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

Posted on | In
Words count in article: 234 | Reading time ≈ 1

题目

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

示例1：

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

解法

解法一：双指针

采用两个指针，p1，p2。

初始时，p1,p2都指向列表头部的dummy节点（加入dummy节点是为了方便处理删除头部的情况），而后，p2向前走n步，p1不动。接着p1,p2同时向前行走，直到p2走到链表末尾，此时，p1刚好指向待删除节点的前一个节点，执行删除操作。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode removeNthFromEnd(ListNode head, int n) {
	    ListNode dummy = new ListNode(0);
	    dummy.next = head;
	    ListNode p1 = dummy;
	    ListNode p2 = dummy;
	    
	    for (int i = 0; i < n + 1; i++) {
	        p1 = p1.next;
	    }
	    while (p1 != null) {
	        p1 = p1.next;
	        p2 = p2.next;
	    }
	    p2.next = p2.next.next;
	    return dummy.next;
	}
0%