一定要早日上岸鸭 · July 17, 2021 0

19. 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 倒数第n个也就是正数第length-n; -->遍历两边 // 快慢指针-->遍历一遍 // 使得快指针到结尾时,慢指针指向倒数第n个点; // ListNode dummy = new ListNode(0); // dummy.next = head; // ListNode fast = dummy, slow=dummy; // int step = n; // while(fast.next!=null){ // System.out.println(fast.val); // while(step>0){ // fast = fast.next; // step--; // } // fast = fast.next; // if(fast == null) break; // slow = slow.next; // } // slow.next = slow.next.next; // return dummy.next; // 相同的思路,不同的实现方式: ListNode dummy = new ListNode(0,head); ListNode first = head; ListNode slow = dummy; // 先让快指针提前动n个单位: for(int i=0; i<n; i++){ first = first.next; } // 然后快慢一起动,当快指针指向null时,慢指针是前n+1个结点 while(first!=null){ first = first.next; slow = slow.next; } // 删除节点 slow.next = slow.next.next; // 返回答案 return dummy.next; } }