链表常见算法题——翻转、删除、哑结点的技巧

1. 翻转链表

题目(原题见LeetCode):

1
2
3
4
5
6
7
8
反转一个单链表。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

1.1 迭代实现

通过迭代遍历每个结点,更改结点的后继引用,就可以很简单地实现链表的反转。例如初始情况下链表的状态如下图:

TIM截图20190108140107.png

第一步,我们头结点a1后继指向NULL,这表示将来它将成为尾结点。并让a2成为头结点:

TIM截图20190108140350.png

第二步,让头结点a2的后继指向a1,让a3成为头结点:

TIM截图20190108140522.png

最后,让头结点a3的后继指向a2。此时,pre便成为了新的反转链表的头结点:

TIM截图20190108140649.png

代码实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode reverseList(ListNode head) {
/* 如果该链表没有头结点或者只有一个头结点,则原样返回head */
if (head == null || head.next == null) return head;

ListNode next = null; // 临时结点,用力保存当前结点的下一结点
ListNode pre = null;

while (head != null) {
next = head.next; // 保存后继节点
head.next = pre; // 让当前的头结点上一个头结点
pre = head; // 当前头结点赋值给pre,将在下一个头结点的后继指向该节点
head = next;
}
return pre; // 返回pre,即反转链表的头结点
}

1.2 递归实现

在反转当前节点之前先反转后续节点。这样从头结点开始,层层深入直到尾结点才开始反转指针域的指向。简单的说就是从尾结点开始,逆向反转各个结点的指针域指向

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}

ListNode reHead = reverseList(head.next);

head.next.next = head;
head.next = null;

return reHead;
}

2. 删除倒数第N个结点

题目(原题见LeetCode):

1
2
3
4
5
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.

该题为链表中快慢双指针的应用,使用的方式非常简单,让快指针先移动n个单位,然后再让快慢指针以相同的速度移动,当快指针到达表尾时,慢指针则为即待删除的结点的前驱。然后通过操作链表的技巧:slow.next = slow.next.next删除slow的后继的结点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) return null;

ListNode fast = head; // 快指针
ListNode slow = head; // 慢指针

/* 先让快指针先移动n个单位 */
for (int i = 0; i < n; i++) {
fast = fast.next;
}
/* 如果删除的是头结点,直接返回头结点的后继 */
if (fast == null) return head.next;
/* 让快指针和慢指针以相同的单位移动,当快指针指向链表末尾时,慢指针则为即待删除的结点的前驱 */
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next; // 删除结点
return head;
}

3. 删除排序链表中的重复元素

题目:原题见LeetCode

1
2
3
4
5
6
7
8
9
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:
输入: 1->1->1->2->3
输出: 2->3

由于这题所给的条件比较简单,链表已经是排好序的了。因此我们这题需要重点需要掌握在处理链表问题时,一个常用的技巧是:面对一些特殊的操作链表问题时(链表的反转、删除、增加),我们可以考虑创建哑结点,使用dummpy -> next表示真正的头结点(head)。这样可以避免判断头指针,统一处理所有的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0); // 创建哑结点
dummy.next = head; // 让哑结点的后继指向真正的子节点
ListNode cur = dummy; // 创建用于遍历结点cur,表示当前结点,其实直接将哑结点作为头结点也可以

while (cur.next != null) {
/* 当下一结点的值会等于下一结点的再下一个结点的值时 */
if (cur.next.next != null && cur.next.val == cur.next.next.val) {
while (cur.next.next != null && cur.next.val == cur.next.next.val) {
cur.next = cur.next.next; // 删除p的后续结点
}
cur.next = cur.next.next;
} else {
cur = cur.next; // 遍历下一个结点
}
}
// 返回真正的头结点
return dummy.next;
}

添加的效果下图所示:

TIM截图20190109142951.png

如图,cur称为了新的头结点,真正的头结点a1则不用作为特殊情况来讨论了。也能符合cur.next.val == cur.next.next.val的判断前提。

4. 合并两个有序链表

题目(原题见LeetCode):

1
2
3
4
5
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

该题的思路是:同时遍历两个链表,比较两个链表当前头结点值的大小,小的值就作为新链表的结点,然后小的值的链表走到下一个元素,大的值链表不动,等待下一次比值。

同样,我们还是需要用到哑结点的操作技巧,最终,dummpy->next指向的就是新链表的真正头结点。

1.png

第一步,当L1的头结点和L2头结点相比较时,L1.val会小于等于L2.val,因此让cur的后继指向L1的头结点,并移动cur到下一个节点:

2.png

第二步,同样比较L1L2,此时L1不满足小于等于L2的条件,因此让cur的后继指向L2,并同样移动到一个节点:

3.png

同样地,第三步又满足了L1.val <= l2.val的条件,让cur的后继指向L1

4.png

直到某一步时,遍历到L1null,只需要直接将L2连接即可:

5.png

最后,便将链表L1L2通过顺序相连,并且哑结点的后继即为真正的头结点:

last.png

代码实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
/* 创建哑结点,这样就不用判断新链表的头结点是l1的头结点还是l2的头结点了 */
ListNode dummy = new ListNode(0);
ListNode cur = dummy;

while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next; // 链表向后1移动一步
} else {
cur.next = l2;
l2 = l2.next; // 链表2向后移动一步
}
cur = cur.next;
}

/* 判断哪个链表先遍历完毕,就将另外一个链表拼接起来就行 */
if (l1 == null) cur.next = l2; // 代表l1先遍历完毕了
if (l2 == null) cur.next = l1; // 代表l2先遍历完毕了

return dummy.next;
}

5. 旋转链表

题目(原题见LeetCode):

1
2
3
4
5
6
7
8
给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。

示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

该题主要的解决步骤是先找到尾结点,并统计链表的长度。然后找到新结点的前驱结点,通过连接尾结点和原先的头结点,并对链表进行切割实现旋转链表。最终的效果如下图:

TIM截图20190109195105.png

代码实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) return head;

/* 首先找到尾节点,并统计链表的长度 */
int count = 1;
ListNode tail = head;
while (tail.next != null) {
count++;
tail = tail.next;
}

k = k % count;
if (k == 0) return head;

ListNode prev = head;
/* 通过迭代找着新的节点的前驱结点 */
for (int i = 0; i < count - k - 1; i++) {
prev = prev.next;
}
ListNode newHead = prev.next; // 保存新的头结点
prev.next = null; // 从新的头结点处断开
tail.next = head;
return newHead;
}
Pushy wechat
欢迎订阅我的微信公众号