代码随想录笔记_链表_19两两交换链表中的节点

代码随想录二刷笔记记录

LC19.删除链表倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

思路：双指针， fast 先走 n 步,之后 slow 和 fast 每次都走一步。双指针第一题

fast 走到 null 时,slow 就指向要删除的节点。

定义一个 pre 指向slow前一个节点，用于断链

代码实现

public ListNode removeNthFromEnd(ListNode head, int n) {
		//定义一个dummy节点和三个指针
        ListNode dummy = new ListNode(-1,head);
        ListNode fast = dummy;
        ListNode slow = dummy;
        ListNode pre = dummy;
     	//fast先走 n 步
        while (n > 0){
            fast = fast.next;
            n--;
        }
		//fast和slow 每次都走一步,直到 fast 为 null
        while (fast != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next;
        }
	    //断链
        pre.next = slow.next;
        slow.next = null;
        return dummy.next;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23