在链表中删除第k个元素（Java实现）

Question

我正在尝试这个程序，但是我无法实现删除。执行进入无限循环。此外，我不知道我是否正确地形成链接列表。

我在下面的程序中缺少什么：

public class SpecificNodeRemoval { 
private static class Node { 
    String item; 
    Node next; 
    Node prev; 

    private Node(String item, Node next, Node prev) { 
     this.item = item; 
     this.next = next; 
     this.prev = prev; 
    } 
} 

public static void main(String[] args) { 
    int k = 3; 

    Node fourth = new Node("Fourth", null, null); 
    Node third = new Node("Third", fourth, null); 
    Node second = new Node("Second", third, null); 
    Node first = new Node("First", second, null); 

    second.prev = first; 
    third.prev = second; 
    fourth.prev = third; 
    Node list = first; 

    Node result = removalKthNode(list, k); 

    int j = 1; 
    while(result.next!=null){ 
     System.out.println(j+": "+result.item); 
    } 
} 

private static Node removalKthNode(Node first, int k) { 
    Node temp = first; 

    for(int i=1; i < k; i++) { 
     temp = temp.next; 
    } 

    temp.prev.next = temp.next; 
    temp.next.prev = temp.prev; 

    return temp; 
} 
} 

---

感谢的回答和评论TON ..工作程序如下：

public class SpecificNodeRemoval { 
private static class Node { 
    String item; 
    Node next; 
    Node prev; 

    private Node(String item, Node next, Node prev) { 
     this.item = item; 
     this.next = next; 
     this.prev = prev; 
    } 
} 

public static void main(String[] args) { 
    int k = 3; 

    Node fourth = new Node("Fourth", null, null); 
    Node third = new Node("Third", fourth, null); 
    Node second = new Node("Second", third, null); 
    Node first = new Node("First", second, null); 

    second.prev = first; 
    third.prev = second; 
    fourth.prev = third; 
    Node list = first; 

    Node result = removalKthNode(list, k); 

    int j = 1; 
    while(result != null){ 
     System.out.println(j+": "+result.item); 
     result = result.next; 
     j++; 
    } 
} 

private static Node removalKthNode(Node first, int k) { 
    Node temp = first; 

    for(int i=1; i < k; i++) { 
     temp = temp.next; 
    } 

    temp.prev.next = temp.next; 
    temp.next.prev = temp.prev; 

    return first; 
} 
} 

的输出是： 1：第一个 2：第二个 3：第四个

Answer 1

这看起来像罪魁祸首。

while(result.next!=null){ 
    System.out.println(j+": "+result.item); 
} 

你没有在链表中前进。

我不完全相信你打算什么，但是你可能需要编写如下，以避免无限循环......

while(result !=null){ 
    System.out.println(j+": "+result.item); 
    result = result.next; 
    j++; 
} 

，如果你想打印整个链表但同样，你不应该使用removeKthNode函数返回的值初始化结果。你应该从开始。

希望这是有道理的。

Answer 2

你在你的代码的几个问题：

1）removalKthNode方法应该返回该列表中的第1个要素，使你的代码打印有意义的结果（或你将不得不重新定位到第1个要素来输出剩余列表

2）打印列表的while循环在两处出错。

a）您不会增加j，所以您始终为项目放置相同的位置。 b）你并没有真的遍历该列表，这意味着你不会重新分配变量result。 尝试是这样的：

int j = 1; 
while (result != null) { 
    System.out.println(j++ + ": " + result.item); 
    result = result.next; 
} 

Answer 3

代码

Node result = removalKthNode(list, k); 
now result = Third 

，你有while循环，而（result.next！= NULL），这是始终处于第三个元素，所以它会无限循环。更改结果如下

while(result!=null){ 
     System.out.println(j+": "+result.item); 
     result = result.next; 
    } 

Answer 4

试试这个：可以帮助你accompalish任务：

package com.amazon; 






class Linkedlist{ 

    Node head; 

    public Linkedlist() { 
     head = null; 
    } 


    public Node addNode(int data){ 

     Node newNode = new Node(data); 
     if(head==null) head = newNode; 
     else{ 
      Node current = head; 
      while(current.next!=null){ 
      current = current.next; 
      } 
      current.next = newNode; 
     } 
     return newNode; 
    } 

} 

class Node 
{ 
    Node next; 
    int data; 

    Node(int d) 
    { 
     data = d; 
     next = null; 
    } 
} 

public class DeleteEveryKthNodes { 



    void modifyList(Node head,int k){ 

     Node current = head; 
     Node previous = null; 
     Node newHead = null; 
     if(current==null)return; 
     int count; 
     while (current != null) { 
      for (count = 1; count < k && current != null; count++) { 
       previous = current; 
       current = current.next; // 1--2--3--4--5 
      } 

      if (current != null) { 
       Node temp = current; 
       previous.next = current.next; 
       // current = null; 
       temp = null; 
       current = current.next; 
      } 
     } 

     current = head; 
     while(current!=null){ 
      System.out.print(" "+current.data); 
      current = current.next; 
     } 
    } 

    public static void main(String args[]) { 


    Linkedlist list = new Linkedlist(); 

    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.head.next.next.next.next = new Node(5); 

    new DeleteEveryKthNodes().modifyList(list.head, 2); 
    //list.head.next.next.next.next = new Node(1); 



} 
}