Fork me on GitHub

leetcode 链表类算法精析(上)

前言

链表是一种特殊的线性结构,由于不能像数组一样进行随机的访问,所以和链表相关的问题有他自身的特点;在面试中十分也是非常容易考到的题目,一般代码比较短,而且能够考查面试者的思维全面性和写无 bug 代码的能力。在写链表的题目时,建议画出示意图。今天我们将会对leetcode这类问题进行总结,所有代码采用 Python 实现,并可以在 LeetCode 里 AC。

链表反转

链表和数组都是线性结构,但是链表和数组的不同在于数组可以随机的对于数据进行访问,给出索引,可以以 O(1) 的时间复杂度迅速访问到该元素。而链表只能从头指针开始。

206. 反转链表(前往该题

题目描述

反转一个单链表。

示例:

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

解题思路

创建一个 prev 节点,表示当前节点的前一个节点,cur 表示当前节点,next 当前节点的下一个节点,不断维护这三个节点,对cur 这个节点进行翻转

paste image

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return head
# 保证prev是一个反转的链表
prev = None
cur = head
while cur != None:
next = cur.next
cur.next = prev
prev = cur
cur = next
return prev

92. 反转链表 II(前往该题

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1
1 ≤ m ≤ n ≤ 链表长度。

示例:

1
2
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解题思路

类似于上一题反转链表的做法,但不同的是只反转中间的一段节点,所以在反转完一段链表后,应重新拼接到原链表对应位置中间。具体步骤为:

  • 首先找到反转链表的首尾节点,同时保存首节点的前一个节点,以便反转完后的拼接
  • 然后按照反转链表的做法维护三个指针,从头到尾一遍遍历调整指针,这样遍历到尾节点时正好反转完指定链表段
  • 最后将原来的首节点next指针指向段后节点

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#coding=utf-8
class Solution:
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
dummyHead = ListNode(0)
dummyHead.next = head
if (m == n):
return head
start = 1
prev = None
cur = head
last = dummyHead
while start <= n:
# last保存要反转字符串的前一个节点
if start == m -1:
last = cur
if start >= m:
next = cur.next
cur.next = prev
prev = cur
cur = next
else:
next = cur.next
cur = next
start += 1
tmp = last.next
last.next = prev
tmp.next = cur
return dummyHead.next

链表的重新整理

83. 删除排序链表中的重复元素(前往该题

题目描述

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

1
2
输入: 1->1->2
输出: 1->2

示例 2:

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

解题思路

充分利用链表有序,要删除一个排序链表的重复元素,重复元素都是挨着的,对于当前节点,判断后一个节点是否与当前节点相同,如果相同删除。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummyHead = ListNode('noval')
dummyHead.next = head
cur = dummyHead
while(cur.next != None):
if cur.next.val == cur.val:
delNode = cur.next
nextNode = delNode.next
cur.next = nextNode
else:
cur = cur.next
return dummyHead.next

86. 分隔链表(前往该题

题目描述

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。

示例:

1
2
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

解题思路

遍历一遍链表,将所有小于 x 的链表按顺序存于 p 链表中, 将所有大于 x 的链表按顺序存于 q 的链表中,最后将 p 链表的尾节点连接 q 链表的首节点。

paste image

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
if head == None:
return head
p = p_min = ListNode(-1)
q = p_max = ListNode(-1)
while head:
if head.val < x:
p.next = head
p = head
else:
q.next = head
q = head
head = head.next
p.next = p_max.next
q.next = None
return p_min.next

328. 奇偶链表(前往该题

题目描述

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

示例 1:

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

示例 2:

1
2
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

说明:

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

解题思路

用两个奇偶指针分别指向奇偶节点的起始位置,另外需要一个单独的指针pre_even来保存偶节点的起点位置,然后把奇节点的指向偶节点的下一个(一定是奇节点),此奇节点后移一步,再把偶节点指向下一个奇节点的下一个(一定是偶节点),此偶节点后移一步,以此类推直至末尾,此时把分开的偶节点的链表连在奇节点的链表后即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def oddEvenList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None or head.next == None:
return head
pre_odd = odd = head
pre_even = even = head.next
# 至少有三个元素
while even and even.next:
odd.next = even.next
even.next = even.next.next
odd = odd.next
even = even.next
odd.next = pre_even
return head

2. 两数相加(前往该题

题目描述

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

示例:

1
2
3
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

解题思路

这道题我做的比较直接,首先遍历 l1 节点,将遍历的数字按照个位、十位、百位…形成一个数字 item1 ,l2 也类似形成数字 item2, 将两数相加和为 ans , 最后将 ans 从个位、十位、百位…组成链表即可。需要注意 0 和边界的处理

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
k = 1
item1 = 0
while l1:
item1 += k * (l1.val)
l1 = l1.next
k *= 10
k = 1
item2 = 0
while l2:
item2 += k * (l2.val)
l2 = l2.next
k *= 10
ans = item1 + item2
if ans == 0:
return ListNode(0)
list1 = []
while ans:
list1.append(ans%10)
ans = ans // 10
p = dummyNode = ListNode(-1)
for one in list1:
temp = ListNode(one)
p.next = temp
p = temp
return dummyNode.next

445. 两数相加 II(前往该题

题目描述

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

进阶:

如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。

示例:

1
2
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

解题思路

这道题我的做法与上一道题做法类似,不同之处在于需要先遍历一遍 l1 和 l2,确定数字个数,从而确定乘 10 的次数, 之后的思想和上题类似。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
list1 = []
n1 = 0
while l1:
list1.append(l1.val)
l1 = l1.next
n1 += 1
item1 = 0
k = pow(10, n1-1)
for one in list1:
item1 += one * k
k = k // 10
list2 = []
n2 = 0
while l2:
list2.append(l2.val)
l2 = l2.next
n2 += 1
item2 = 0
k = pow(10, n2-1)
for one in list2:
item2 += one * k
k = k // 10
ans = item1 + item2
if ans == 0:
return ListNode(0)
list1 = []
while ans:
list1.insert(0, ans%10)
ans = ans // 10
p = dummyNode = ListNode(-1)
for one in list1:
temp = ListNode(one)
p.next = temp
p = temp
return dummyNode.next

设立链表的虚拟头结点

很多涉及到链表的操作,如果不设立链表的头结点,需要做很多额外的判断和操作,通常一些操作的逻辑对于链表的第一个节点不适用,需要特殊处理,而有了虚拟节点就可以一视同仁了。下面看一些 leetcode203 这道题。

203. 删除链表中的节点(前往该题

题目描述

删除链表中等于给定值 val 的所有节点。

示例:

1
2
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

不使用虚拟头结点

解题思路

paste image

上面的逻辑对删除最后一个元素依然适用,但是对于对删除第一个元素不适用

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 不使用虚拟头结点
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
while( head != NULL && head->val == val ){
ListNode* node = head;
head = head->next;
delete node;
}
if( head == NULL )
return head;
ListNode* cur = head;
while( cur->next != NULL ){
if( cur->next->val == val ){
ListNode* delNode = cur->next;
cur->next = delNode->next;
delete delNode;
//delNode -> next = NULL;
}
else
cur = cur->next;
}
return head;
}
};

使用虚拟头结点

解题思路

paste image

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
dummyNode = ListNode(-1)
dummyNode.next = head
cur = dummyNode
while cur.next:
p = cur.next
if p.val == val:
cur.next = p.next
else:
cur = cur.next
return dummyNode.next

82. 删除排序链表中的重复元素 II(前往该题

题目描述

给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

示例 1:

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

示例 2:

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

解题思路

首先对于链表的删除操作,如果没有虚拟头节点,需要对头节点进行特殊的处理,我们这里设置虚拟头节点。相比于上一题题。我们增加一个 p 来记录重复元素前面的节点即可

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None or head.next == None:
return head
dummyNode = ListNode(-1)
dummyNode.next = head
cur = dummyNode.next
p = dummyNode
while cur and cur.next:
q = cur.next
if q.val == cur.val:
while q and q.val == cur.val:
q = q.next
p.next = q
cur = q
else:
p = cur
cur = cur.next
return dummyNode.next

总结

链表是一种特殊的线性结构,由于不能像数组一样进行随机的访问,所以和链表相关的问题有他自身的特点;在面试中十分也是非常容易考到的题目。我们在准备面试的时候,刷算法题是一种捷径,特别是刷 LeetCode,但是不能一味的刷题,我们需要总结和思考,对于一些相似的题目我们应该多想想他们的思想,其实很多题的解题思路都是相近的。

-------------本文结束 感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!