时间戳

首页 > 解决方案 > 按规则访问节点，删除链表中所有未访问的节点

java - 按规则访问节点，删除链表中所有未访问的节点

问题描述

我试图根据链表中头指针的值遍历链表，因为一个节点包含两个值，即当前值和指向下一个的指针。我必须按照以下方式穿越 在此处输入图像描述

最初，您处于领先地位（值为 1 的节点）。因此，您移至第一个节点之后，即值为 2 的节点。

从节点 2 开始，您访问第二个节点，即值为 1 的节点。

以类似的方式，您转到倒数第二个节点（值 = 2）。

从那里开始，因为少于 2 个节点，您到达 NULL 并停止。

因此，访问的节点是 1、2、1 和 2

 /*
    public class ListNode {
       public int val; 
       public ListNode next;
       public ListNode(int x) { val = x; next = null; }
    }
    */
    
    public class Solution {
        satic void deleteUnvisitedNodes(ListNode head) {
            ListNode current = head;
            ListNode temp;
            while(current != null){
                int k = current.val;
                temp = NthNode(current,k);
                current.next = temp.next;
            }
        }
    
           static  ListNode NthNode(ListNode head, int k){
                int count = 0;
                ListNode current = head;
                while(current !=null && current.next!=null){
                    if(count == k)
                        return current;
                    count++;
                    current = current.next;
                    }
                    return current;
                }
              public static void main(String[] args){
    ListNode head = null;
    head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(1);
    head.next.next.next.next = new ListNode(2);
    head.next.next.next.next.next = new ListNode(3);
    ArrayList<ListNode> l = new ArrayList<>();
    deleteUnvisitedNodes(head);
    while(head != null){
        l.add(head);
        head = head.next;
    }
    System.out.print(l);
}

我收到运行时错误

标签： javalinked-list

解决方案

问题是您在删除方法中未访问的节点后没有继续前进，deleteUnvisitedNodes这会导致无限次数的执行并因此超时。因此，在删除未访问的节点后，我们需要继续前进到该N-th节点并继续该过程。
这是具有所需输出的工作代码：

class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int x)
    { val = x; next = null; }
}
class Solution
{
    void deleteUnvisitedNodes(ListNode head)
    {
        ListNode current = head;
        ListNode temp;
        while (current != null)
        {
            int k = current.val;
            temp = NthNode(current,k);
            current.next = temp;
            current = current.next; // or current = temp // <-- Modified
        }
    }
    
    ListNode NthNode(ListNode head, int k)
    {
        int count = 0;
        ListNode current = head;
        while (current != null && current.next != null)
        {
            if (count == k)
                return current;
            ++count;
            current = current.next;
        }
        return null; // <-- Modified
    }
    public static void main (String[] args)
    {
        ListNode a = new ListNode(1); ListNode b = new ListNode(2);
        ListNode c = new ListNode(3); ListNode d = new ListNode(1);
        ListNode e = new ListNode(2); ListNode f = new ListNode(3);
        
        a.next = b; b.next = c; c.next = d; d.next = e; e.next = f;
        ListNode head = a;
        while (head != null)
        {
            System.out.print(head.val + " -> ");
            head = head.next;
        }System.out.println("null");
        
        Solution sol = new Solution();
        sol.deleteUnvisitedNodes( a );
        
        head = a;
        while (head != null)
        {
            System.out.print(head.val + " -> ");
            head = head.next;
        }System.out.println("null");
    }
}

输出 ：

1 -> 2 -> 3 -> 1 -> 2 -> 3 -> null
1 -> 2 -> 1 -> 2 -> null
如有任何疑问，请随时提出。

推荐阅读