[LeetCode]19. Remove Nth Node From End of List删除链表的倒数第N个节点

怼烎@ 2022-10-02 14:57 12阅读 0赞

Given a linked list, remove the *n*\-th node from the end of list and return its head.

**Example:**

Given linked list: 1->2->3->4->5, and n = 2.
    
    After removing the second node from the end, the linked list becomes 1->2->3->5.

**Note:**

Given *n* will always be valid.

**Follow up:**

Could you do this in one pass?

题目要求删除一个节点，但是给出的是倒数的节点，如果是正数的节点一次遍历过去就可以了，但是倒数的节点似乎不能这么做。

其实还是可以一次遍历删除节点，我们先设置一个指针i，往前推n个，这个时候再设置第二个指针j，两个指针i和j同时往前推，这样当

i抵达链表结尾时j的位置正好是倒数第n个节点，此时把节点j删除就可以了（测试样例中有个特殊例子，输入\[1\],这里要特殊化处理）

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode res=new ListNode(0);
            res.next=head;
            ListNode l1=res;
            ListNode l2=res;
            for(int i=1;i<=n+1;i++){
                l1=l1.next;
            }
            while(l1!=null){
                l2=l2.next;
                l1=l1.next;
            }
            l2.next=l2.next.next;
            return res.next;
        }
    }

转载于:https://www.cnblogs.com/jchen104/p/10238325.html