从链表末尾删除第 K 个节点

Question

除了我想删除列表中的第一个节点外，一切都在工作if (kthToLast == 0) head = head.next;。我不知道为什么它不删除第一个元素，因为head = head.next;应该工作。

谢谢。

// 2.2 Implement an algorithm to find the kth to last element of a singly linked list.
public class RemoveKthToLast {
    static Node head;
    static int count = 0;
    public static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            next = null;
            count++;
        }
    }
    public Node removeKthToLast(Node head, int n) {
        if (head == null || n < 1)
            System.out.println("invalid");;
        int count = 0;
        Node temp = head;
        while (temp != null) { // count number of nodes in list
            temp = temp.next;
            count++;
        }
        if (n > count)
            System.out.println("n is greater than length of list");;
        int kthToLast = count - n;
        // remove first node 
        if(kthToLast == 0) 
             head = head.next;
        for (int i = 0; i < kthToLast - 1; i++) 
            head = head.next;
        head.next = head.next.next;
        return head;
    }
    // prints out contents of linked-list
    public void toString(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
    public static void main(String args[]) {
        RemoveKthToLast list = new RemoveKthToLast();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(4);
        list.removeKthToLast(head, 0);
        list.toString(head);
    }
}

Answer 1

问题是，即使您尝试删除链表中的第一个节点，您仍然可以继续使用该方法的其余部分，这只应在尝试删除第一个节点以外的节点时执行。例如，假设您正在尝试移除头部。是的，head 字段将更新到列表中的第二个节点。但是，该方法并没有就此结束，而是执行行head.next = head.next.next这将错误地删除链表中的第 3 个节点。因此，解决方案是在重置头部字段后基本上结束该方法。

public Node removeKthToLast(Node head, int n) {
    if (head == null || n < 1)
        System.out.println("invalid");;
    int count = 0;
    Node temp = head;
    while (temp != null) { // count number of nodes in list
        temp = temp.next;
        count++;
    }
    if (n > count)
        System.out.println("n is greater than length of list");;
    int kthToLast = count - n;
    // remove first node 
    if(kthToLast == 0){
         head = head.next;
         return head;//end the method here when removing the 1st node
    }
    for (int i = 0; i < kthToLast - 1; i++) 
        head = head.next;
    head.next = head.next.next;
    return head;
    }

此外，请确保在主节点中更新列表的头节点。

list.head = list.removeKthToLast(head,4);

Answer 2

如果唯一的问题是第一个节点没有被删除，那么试试这个

// remove first node 
if(kthToLast == 0) {
     head = head.next;
     return head;
}

Answer 3

只是一个建议：你可以在这里使用递归函数，你的代码将非常简单：

public Node removeKthFromLast(Node head, int k) {
    int n;
    Node p = head;
    for (n=0;head != null;n++) {
      p = head.next;
    }
    return removeKthFromLastAux(head, n-k);
}
private Node removeKthFromLastAux(Node head, int ik) {
    if (head == null) {
        return null;
    }
    if (ik == 0) {
        return head.next;
    }
    head.next = removeKthFromLastAux(head, ik-1);
    return head;
}