Recursive solution for truncating a linked list

user_17138291 0
Viewed 56
public class Solution {

  /**
   * Return a list containing, at most, the first numNodes nodes in the list starting with head. If
   * numNodes is larger than the length of the list, then the entire list will be returned.
   * 
   * Examples:
   * 
   * <pre>
   * [11, 12, 13], numNodes = 2
   * returns [11, 12]
   * 
   * [11, 12, 13], numNodes = 0
   * returns []
   * 
   * [11, 12, 13], numNodes = 100
   * returns [11, 12, 13]
   * 
   * [], numNodes = 5
   * returns []
   * </pre>
   * 
   * @param head - Head of the list to truncate
   * @param numNodes - Maximum number of nodes in the resulting list
   * @return head of the truncated list
   */
  public static ListNode truncate(ListNode head, int numNodes) {
    // just return null
    if (head == null) {
      return null;
    }
    // Recursion head.next
    if (head.next != null) {
      head.next = truncate(head.next, numNodes--);
    }
    
    if (numNodes <= 0) {
      return head.next;
    } else {
      return head;
    }
  }

As you can see, the purpose of this code is to truncate every node past numNodes. Im passing every test besides the situation where a list of length 4 is passed through and I need to return the first 3 nodes(numNodes = 3). If anyone could help me out, that would be much appreciated. I don't know what Im doing wrong.

heres the ListNode class

/**
 * Simple Singly-linked-list node.
 */
public class ListNode {

  public int val;
  public ListNode next;

  public ListNode(int val, ListNode next) {
    this.val = val;
    this.next = next;
  }

  public ListNode(int val) {
    this.val = val;
    this.next = null;
  }

  public ListNode() {
    this.val = 0;
    this.next = null;
  }
}

here is the only test I'm failing

testTruncateLengthFourListToThree() expected: [10, 11, 12] actual: [10, 11, 12, 13]

Solution has to be recursive.

truncate recursion linked-list java
2 Answers

Try this.

record ListNode(int val, ListNode next) {}

public static ListNode truncate(ListNode head, int numNodes) {
    if (head == null || numNodes <= 0)
        return null;
    else
        return new ListNode(head.val, truncate(head.next, numNodes - 1));
}

public static String toString(ListNode head) {
    List<String> list = new ArrayList<>();
    for ( ; head != null; head = head.next)
        list.add("" + head.val);
    return list.toString();
}

public static void main(String[] args) {
    ListNode list = new ListNode(1, new ListNode(2, new ListNode(3, null)));
    System.out.println("list = " + toString(list));
    System.out.println("truncate(list, 3) = " + toString(truncate(list, 3)));
    System.out.println("truncate(list, 2) = " + toString(truncate(list, 2)));
    System.out.println("truncate(list, 1) = " + toString(truncate(list, 1)));
    System.out.println("truncate(list, 0) = " + toString(truncate(list, 0)));
}

output:

list = [1, 2, 3]
truncate(list, 3) = [1, 2, 3]
truncate(list, 2) = [1, 2]
truncate(list, 1) = [1]
truncate(list, 0) = []
Admin1

Maybe you can use prefix increment instead of postfix at the recursive call to truncate, changing from truncate(head.next, numNodes--) to truncate(head.next, --numNodes) so that numNodes is decremented before the recursion.

user_35865700
Related