岁月轻狂

链表review


链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。——维基百科

链表和数组都是一种线性结构

  • 数组是一段连续的存储空间
  • 链表空间不一定保证连续,为临时分配的。

链表的分类

按连接方向分类

  • 单链表
  • 双链表

按照有环无环分类

  • 普通链表
  • 循环链表

链表问题代码实现的关键点

1.链表调整函数的返回值类型,根据要求往往是节点类型
2.处理链表过程中,先采用画图的方式理清逻辑
3.链表问题对于边界条件讨论要求严格

链表插入和删除的注意事项:

1.特殊处理链表为空,或者链表长度为1 的情况
2.注意插入时的操作过程
3.注意删除操作的调整过程
注意点:头尾节点及空节点需特殊考虑

双链表的插入与删除和单链表类似,但是需要额外考虑previous指针的指向。

单链表分翻转操作
当链表为空或者长度为1时,特殊处理

注意

1.大量链表问题可以使用额外数据结构来简化调整过程
2.但链表问题最优解往往是不使用额外数据结构的方法

环形链表插值

有一个整数val,如何在节点值有序的环形链表中插入一个节点值为val的节点,并且保证这个环形单链表依然有序。

给定链表的信息,及元素的值A及对应的nxt指向的元素编号同时给定val,请构造出这个环形链表,并插入该值。

测试样例:
[1,3,4,5,7],[1,2,3,4,0],2
返回:{1,2,3,4,5,7}

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
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class InsertValue:
def insert(self, A, nxt, val):
#先构造出要插入的节点
nodeT=ListNode(val)
if not A:
nodeT.next = NodeT
return nodeT
#接下来要构造环形单链表
head=ListNode(A[0])
r=head
for i in range(len(A)-1):
r.next=ListNode(A[nxt[i]])
r=r.next
#先边界处理
if head.val>val:
#r.next=nodeT
nodeT.next=head
head=nodeT
return head
if r.val<val:
r.next=nodeT
nodeT.next=None
return head
#中间插值
pre,now=head,head.next
while True:
if pre.val<=val and now.val>=val:
break
else:
pre=pre.next
now=now.next
pre.next=nodeT
nodeT.next=now
return head
# write code here

访问单个节点的删除

实现一个算法,删除单向链表中间的某个结点,假定你只能访问该结点。

给定带删除的节点,请执行删除操作,若该节点为尾节点,返回false,否则返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Remove:
def removeNode(self, pNode):
# write code here
self.pNode = pNode
if self.pNode.next == None:
return False
else:
self.pNode = self.pNode.next
return True

注意:
该删除方式并不是删除了该删除的节点,而是进行了值的拷贝。
1.结构复制且拷贝操作受限时,不可行
2.在工程上影响外部依赖

链表的分化

对于一个链表,我们需要用一个特定阈值完成对它的分化,使得小于等于这个值的结点移到前面,大于该值的结点在后面,同时保证两类结点内部的位置关系不变。

给定一个链表的头结点head,同时给定阈值val,请返回一个链表,使小于等于它的结点在前,大于等于它的在后,保证结点值不重复。

测试样例:
{1,4,2,5},3
{1,2,4,5}

解决思路:
简单做法:
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
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Divide:
def listDivide(self, head, val):
llst, rlst = [], []
cur = head
if head == None: return None
count = 0
while cur != None:
count += 1
tmp = ListNode(cur.val)
if tmp.val <= val:
llst.append(tmp)
else:
rlst.append(tmp)
cur = cur.next
llst += rlst
for s in xrange(count - 1):
llst[s].next = llst[s + 1]
return llst[0]

打印两个链表的公共值

现有两个升序链表,且链表中均无重复元素。请设计一个高效的算法,打印两个链表的公共值部分。

给定两个链表的头指针headA和headB,请返回一个vector,元素为两个链表的公共部分。请保证返回数组的升序。两个链表的元素个数均小于等于500。保证一定有公共值

测试样例:
{1,2,3,4,5,6,7},{2,4,6,8,10}
返回:[2.4.6]

解决思路:
如果两个链表有任何一个为空,直接返回即可。
如果都不为空,则从两个链表的头节点开始遍历。接下来:
如果list1 当前节点的值小于list2当前节点的值,则继续遍历list1的下一个节点。
如果list2 当前节点的值小于list1当前节点的值,则继续遍历list2的下一个节点。
如果list1 和 lsit2,当前节点值相等,则打印当前节点值,然后都向下移动。
list 1 或者list2 当前节点值中有一个为空时,结束整个过程。

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
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Common:
def findCommonParts(self, headA, headB):
# write code here
#如果两个链表有任何一个为空,直接返回即可。
if headA == None or headB == None:
return None
listc = []
#如果两个链表都不为空,则从头开始遍历
while headA != None and headB != None:
#如果listA 当前节点的值小于listB当前节点的值,则继续遍历listB的下一个节点。
if headA.val < headB.val:
headA = headA.next
#如果listA 当前节点的值小于listB当前节点的值,则继续遍历listB的下一个节点。
elif headA.val > headB.val:
headB = headB.next
#如果listA 和 lsitB,当前节点值相等,则打印当前节点值,然后都向下移动。
else:
listc.append(headA.val)
headA = headA.next
headB = headB.next
return listc

链表的k逆序

有一个单链表,请设计一个算法,使得每K个节点之间逆序,如果最后不够K个节点一组,则不调整最后几个节点。例如链表1->2->3->4->5->6->7->8->null,K=3这个例子。调整后为,3->2->1->6->5->4->7->8->null。因为K==3,所以每三个节点之间逆序,但其中的7,8不调整,因为只有两个节点不够一组。

给定一个单链表的头指针head,同时给定K值,返回逆序后的链表的头指针。

解决思路:
如果链表为空,或长度为1,或k < 2,链表不用进行调整
方法1: 时间复杂度为O(n),额外空间复杂度为O(k).
利用栈来处理,将k个元素依次进栈,然后依次从栈中弹出。
下一组元素继续按上面过程处理。
如果最后一组元素不足k个,则不调整。
方法2: 时间复杂度为O(n),额外空间复杂度为O(1).
1.基本过程与方法一类似
2.依然是每收集k个元素就做逆序调整
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class KInverse:
def reverse(self, head, count):
pre, nxt = None, None
while count:
nxt = head.next
head.next = pre
pre = head
head = nxt
count -= 1
return pre
def inverse(self, head, k):
# write code here
count = 0
cur = head
tmp = head
root, tail = None, head
res = head
while cur:
count += 1
if count == k:
cur = cur.next
if not root:
res = self.reverse(tmp, k)
root = res
else:
root = self.reverse(tmp, k)
tail.next = root
tail = tmp
tmp.next = cur
tmp = tmp.next
count = 0
continue
else:
cur = cur.next
return res

链表指定值清除

现在有一个单链表。链表中每个节点保存一个整数,再给定一个值val,把所有等于val的节点删掉。

给定一个单链表的头结点head,同时给定一个值val,请返回清除后的链表的头结点,保证链表中有不等于该值的其它值。请保证其他元素的相对顺序。

测试样例:
{1,2,3,4,3,2,1},2
{1,3,4,3,1}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
-*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class ClearValue:
def clear(self, head, val):
#遍历节点,当节点值与val值相等时,修改指针
#如果节点为空,直接返回
if head == None:
return head
pre ,curl = ListNode(-1) ,head
nhead = pre
pre.next = curl
while curl != None:
if curl.val == val:
pre.next = curl.next
else:
pre = curl
curl = curl.next
return nhead.next

链表的回文结构

请编写一个函数,检查链表是否为回文。

给定一个链表ListNode* pHead,请返回一个bool,代表链表是否为回文。

测试样例:
{1,2,3,2,1}
返回:true
{1,2,3,2,3}
返回:false

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
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Palindrome:
def isPalindrome(self, pHead):
#如果pHead为空,直接返回false
if pHead == None:
return False
#用两个指针分别指向头和尾,从两边往中间扫,如果从始自终,所指字符都相等,则返回true 否则,返回false
node = pHead
temp = []
while node != None:
temp.append(node.val)
node = node.next
front = 0
back = len(temp) - 1
while front < back:
if temp[front] == temp[back]:
front += 1
back -= 1
else:
return False
return True

方法二:利用栈,先入栈,然后依次pop,与链表值进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Palindrome:
def isPalindrome(self, pHead):
p = pHead
stack = []
while p != None:
stack.append(p.val)
p = p.next
while stack:
if stack.pop() == pHead.val:
pHead = pHead.next
else:
return False
return True

链表判环

如何判断一个单链表是否有环?有环的话返回进入环的第一个节点的值,无环的话返回-1。如果链表的长度为N,请做到时间复杂度O(N),额外空间复杂度O(1)。

给定一个单链表的头结点head(注意另一个参数adjust为加密后的数据调整参数,方便数据设置,与本题求解无关),请返回所求值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class ChkLoop:
def chkLoop(self, head, adjust):
if not head: #链表为空
return -1
slowp,fastp=head,head #p慢指针 q快指针
while fastp.next and fastp.next.next:
slowp=slowp.next
fastp=fastp.next.next
if fastp==slowp:
break
if not fastp.next or not fastp.next.next:
return -1
fastp=head
while fastp!=slowp:
fastp=fastp.next
slowp=slowp.next
return fastp.val

无环单链表判相交

现在有两个无环单链表,若两个链表的长度分别为m和n,请设计一个时间复杂度为O(n + m),额外空间复杂度为O(1)的算法,判断这两个链表是否相交。

给定两个链表的头结点headA和headB,请返回一个bool值,代表这两个链表是否相交。保证两个链表长度小于等于500。
方法一:哈希表实现,一个链表加入Hash表中,遍历另一个链表,一旦遇到某个节点在hash表中有记录,则说明有交点,且为第一个交点

方法二:
假设链表1的长度为m, 链表2的长度为n,且 m > n, 则 先遍历链表1走m -n步,接着俩个链表同时遍历,遇到相等的节点极为相交点。

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
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class CheckIntersect:
def chkIntersect(self, headA, headB):
# 差值处理
if not headA or not headB:
return False
lenA, lenB = 0, 0
pA, pB = headA, headB
while pA :
lenA += 1
pA = pA.next
while pB:
lenB += 1
pB = pB.next
pA, pB = headA, headB
if lenA > lenB:
distance = lenA - lenB
for i in range(distance): pA = pA.next
else:
distance = lenB - lenA
for i in range(distance): pB = pB.next
while pA:
if pA == pB: return True
pA , pB = pA.next, pB.next
return False

有环单链表相交判断

如何判断两个有环单链表是否相交?相交的话返回第一个相交的节点,不想交的话返回空。如果两个链表长度分别为N和M,请做到时间复杂度O(N+M),额外空间复杂度O(1)。

给定两个链表的头结点head1和head2(注意,另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。

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
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class ChkIntersection:
def chkInter(self, head1, head2,adjust0, adjust1):
loop1 = self.chkLoop(head1)
loop2 = self.chkLoop(head2)
if loop1 == loop2:
return True
p = loop1.next
while p != loop1:
if p == loop2:
return True
p = p.next
return False
def chkLoop(self, head):
p1, p2 = head, head
while True:
p1 = p1.next
p2 = p2.next.next
if p1 == p2:
return p1

单链表相交判断

给定两个单链表的头节点head1和head2,如何判断两个链表是否相交?相交的话返回true,不想交的话返回false。

给定两个链表的头结点head1和head2(注意,另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。

解决思路:

1.利用案例九的方法找到两个链表各自的入环节点。
假设:head1链表的入环节点为node1
head2链表的入环节点为node2
2.如果node1 和 node2, 一个为空,另一个不为空,则两个链表不可能相交
3.如果node1 和 node2 都等于空, 则说明两个链表都无环,则用上面”无环单链表判相交”解决方法解决
4.如果node1 和 node2 都不为空,说明两个链表都有环,则用上面“有环单链表相交判断”的方法进行判断。

代码实现:

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
58
59
60
61
62
63
64
65
66
67
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class ChkIntersection:
def chkInter(self, head1, head2, adjust0, adjust1):
# write code here
if head1 == None or head2 == None:
return False
#找到两个链表各自的入环节点
p1,p2 = self.chkLooper(head1),self.chkLooper(head2)
#如果node1 和 node2 都等于空, 则说明两个链表都无环,则用"无环单链表判相交"解决方法
if p1 == None and p2 == None:
n, m = 0,0
node1 = head1
node2 = head2
while node1 != None:
node1 = node1.next
n += 1
while node2 != None:
node2 = node2.next
m += 1
if m >= n:
long = head2
short = head1
k = m - n
else:
long = head1
short = head2
k = n - m
for i in xrange(0,k):
long = long.next
while long != short and long != None:
long = long.next
short = short.next
if long == None:
return False
else:
return True
#如果node1 和 node2, 一个为空,另一个不为空,则两个链表不可能相交
elif p1 == None or p2 == None:
return False
#如果node1 和 node2 都不为空,说明两个链表都有环,则用“有环单链表相交判断”的方法进行判断。
else:
if p1 == p2:
return True
p = p1.next
while p != p1:
if p == p2:
return True
p = p.next
return False
#找到入环节点
def chkLooper(self,head):
p1,p2 = head,head
while 1:
p1 = p1.next
if p2.next == None:
return None
p2 = p2.next.next
if p1 == None or p2 == None:
return None
if p1 == p2:
return p1

思考题

复杂链表的复制
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点)。

mindthink wechat
扫一扫,关注我的微信公众号!