剑指offer题解 - 链表

Posted on | Post modified: | In
Words count in article: 2.7k

本系列为剑指offer刷题笔记，刷题平台为牛客网。

本文主要是链表相关题目题解总结。

[TOC]

3. 从尾到头打印链表

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

解题思路

使用Python库函数，新建一个列表，使用insert每次插入到最前面，或者使用append最后在使用reverse。

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
# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# 单向链表链表 node1: 1->2->3
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4

class Solution:
    def printListFromTailToHead(self, listNode):
        # 方法1：使用insert函数
        # c = []
        # while listNode:
        #     c.insert(0,listNode.val)
        #     listNode = listNode.next
        # return c

        # 方法2：使用append，最后reverse
        c = []
        while listNode:
            c.append(listNode.val)
            listNode = listNode.next
        c.reverse()
        return c

if __name__ == '__main__':
    run = Solution()
    result = run.printListFromTailToHead(node1)
    print(result)

14.链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

解题思路

三个特例：

  • 如果输入的链表为空；
  • k大于链表的长度；
  • k为0的情况。

对于正常情况，设置两个指针分别指向头结点，第一个指针向前走k-1步，走到正数第k个结点，同时保持第二个指针不动，然后第一个指针和第二个指针每次同时前移一步，这样第一个指针指向尾结点的时候，第二个指针指向倒数第k个结点。判断尾结点的条件是 p.next == None。

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
# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# 单向链表链表 node1: 1->2->3
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4

class Solution:
    def FindKthToTail(self, head, k):
        if not head or k <= 0:
            # 链表为空或k小于等于0
            return None
        p = head
        q = head
        for i in range(1,k):
            if p.next == None:
                # k大于链表的长度
                return None
            else:
                p = p.next
        while p.next:
            p = p.next
            q = q.next
        return q

if __name__ == '__main__':
    originList = node1
    print('链表:',end = ' ')
    while originList:
        print(originList.val, end = ' ')
        originList = originList.next
    k = 5
    result = Solution().FindKthToTail(node1,k)
    print('\n倒数第{0}个结点:'.format(k),end = ' ')
    while result:
        print(result.val,end = ' ')
        result = result.next

推广: 寻找中间节点, 两个指针一起, 第一个指针每次走两步, 第二个指针每次走一步, 快指针指到尾部, 慢指针正好指到中间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 def FindMidNode(self,head):
        """
        推广: 寻找中间节点, 两个指针一起,
        第一个指针每次走两步, 第二个指针每次走一步,
        快指针指到尾部, 慢指针正好指到中间
        """
        if not head:
            return None
        p = head
        q = head
        p = p.next
        while p:
            p = p.next
            if p:
                p = p.next
                q = q.next
        return q

mid = Solution().FindMidNode(node1)
    print('\n中间结点:',end = ' ')
    while mid:
        print(mid.val, end = ' ')
        mid = mid.next

15.反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

解题思路

迭代

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 Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return pHead
        
        dummy = ListNode(0)
        dummy.next = pHead
        cur = pHead.next
        pHead.next = None
        
        while cur:
            temp = cur.next
            cur.next = dummy.next
            dummy.next = cur
            cur = temp
            
        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
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return pHead
        
        return self.helper(pHead, ListNode(0))
    
    def helper(self, cur, dummy):
        if not cur:
            return dummy.next
        temp = cur.next
        cur.next = dummy.next
        dummy.next = cur
        cur = temp
        return self.helper(cur, dummy)

16 合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解题思路

思路1：循环：如果两个链表不为空，进行比较，将小的赋给合并的指针头，小的链表走一步，合并链表走一步，如果有一个为空，跳出循环，并将另一不为空的链表后续部分赋给合并链表

思路2：递归：如果第一个链表为空，则返回第二个链表，如果第二个链表为空，则返回第一个链表，如果两个链表都为空，结果为空
两个链表都是排序好的，我们只需要从头遍历链表，判断当前指针，哪个链表的值小，即赋给合并链表指针。

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
# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

node1 = ListNode(1)
node2 = ListNode(3)
node3 = ListNode(5)
node1.next = node2
node2.next = node3
node4 = ListNode(2)
node5 = ListNode(4)
node6 = ListNode(6)
node4.next = node5
node5.next = node6

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # 循环
        # newHead = ListNode(-1)
        # pre = newHead
        # while pHead1 and pHead2:
        #     if pHead1.val < pHead2.val:
        #         pre.next = pHead1
        #         pHead1 = pHead1.next
        #     else:
        #         pre.next = pHead2
        #         pHead2 = pHead2.next
        #     pre = pre.next
        # pre.next = pHead1 if pHead1 else pHead2
        # return newHead.next

        # 递归
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        newHead = None
        if pHead1.val < pHead2.val:
            newHead = pHead1
            newHead.next = self.Merge(pHead1.next, pHead2)
        else:
            newHead = pHead2
            newHead.next = self.Merge(pHead1, pHead2.next)
        return newHead


if __name__ == '__main__':
    result = Solution().Merge(node1,node4)
    print('合并链表：',end = ' ')
    while result:
        print(result.val,end = ' ')
        result = result.next

25 复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解题思路

我们这里将复杂链表的复制过程分解为三个步骤。在写代码的时候我们每一步定义一个函数，这样每个函数完成一个功能，整个过程的逻辑也就非常清晰明了了。
我们这里采用三步：
第一步：复制复杂指针的label和next。但是这次我们把复制的结点跟在元结点后面，而不是直接创建新的链表；
第二步：设置复制出来的结点的random。因为新旧结点是前后对应关系，所以也是一步就能找到random；
第三步：拆分链表。奇数是原链表，偶数是复制的链表。
有图思路更清晰：



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
# -*- coding:utf-8 -*-
class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None

# 复杂链表
node1 = RandomListNode(1)
node2 = RandomListNode(2)
node3 = RandomListNode(3)
node4 = RandomListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node1.random = node3
node2.random = node4
node3.random = node2
node4.random = node1

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return pHead
        # 复制节点在源节点后面
        cur = pHead
        while cur:
            temp = cur.next
            cur.next = RandomListNode(cur.label)
            cur.next.next = temp
            cur = temp
        #复杂随机节点
        cur = pHead
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        #分离新旧节点
        res = pHead.next
        temp = res
        cur = pHead
        while cur:
            cur.next = cur.next.next
            if temp.next:
                temp.next = temp.next.next
            cur = cur.next
            temp = temp.next
        
        return res

if __name__ == '__main__':
    result = Solution().Clone(node1)
    while result:
        print(result.label, end = ' ')
        result = result.next

36 两个链表的第一个公共结点

题目描述

输入两个链表，找出它们的第一个公共结点。

解题思路

思路1：把两个链表拼接起来，一个pHead1在前pHead2在后，一个pHead2在前pHead1在后，这样，生成了两个相同长度的链表，我们只要同时遍历这两个表，就一定能找到公共节点。时间复杂度O(m+n)，空间复杂度O(m+n).

思路2：首先依次遍历两个链表，记录两个链表的长度m和n，如果 m > n，那么我们就先让长度为m的链表走m-n个结点，然后两个链表同时遍历，当遍历到相同的结点的时候停止即可。对于 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
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
# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node6 = ListNode(6)
node1.next = node2
node2.next = node5
node5.next = node6
node3.next = node4
node4.next = node5
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # 方法1
        # if not pHead1 or not pHead2:
        #     return None
        # cur1, cur2 = pHead1, pHead2
        # while cur1 != cur2:
        #     cur1 = cur1.next if cur1 else pHead2
        #     cur2 = cur2.next if cur2 else pHead1
        # return cur1

        # 方法2
        if not pHead1 or not pHead2:
            return None
        m = n = 0
        cur1, cur2 = pHead1, pHead2
        while cur1:
            m += 1
            cur1 = cur1.next
        while cur2:
            n += 1
            cur2 = cur2.next
        if m > n:
            for i in range(m-n):
                pHead1 = pHead1.next
            while pHead1:
                if pHead1 == pHead2:
                    return pHead1
                pHead1, pHead2 = pHead1.next, pHead2.next
        else:
            for i in range(n-m):
                pHead2 = pHead2.next
            while pHead1:
                if pHead1 == pHead2:
                    return pHead1
                pHead1, pHead2 = pHead1.next, pHead2.next
        return None

if __name__ == '__main__':
    result = Solution().FindFirstCommonNode(node1, node3)
    while result:
        print(result.val, end = ' ')
        result = result.next

55 链表中环的入口结点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解题思路

第一步：判断是否存在环，用快慢指针，一个走一步，一个走两步，如果最终达到同一节点，则说明有环

第二步：寻找环的入口，假设入口结点距离头结点a个单位，fast和slow相遇在距离入口结点b个单位的位置，环剩下的长度为c，则有a+b+c+b = 2*(a+b) —> a = c 。因此，在重合时候，将fast置为head，再一步一步地走，当与slow重合时的结点即为入口结点。

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
# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self,x):
        self.val = x
        self.next = None

node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return None
        fast = slow = pHead
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                # 有环
                fast = pHead
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return fast
        return None

if __name__ == '__main__':
    result = Solution().EntryNodeOfLoop(node1)

56 删除链表中重复的结点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

解题思路

要删除有序链表中所有的重复节点，而头结点有可能就是重复节点。这样的比较好的解决方式就是新建头结点，然后往后遍历，同样的值就全部略过。

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
# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(3)
node5 = ListNode(4)
node6 = ListNode(4)
node7 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6
node6.next = node7

class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return pHead
        first = ListNode(-1)
        first.next = pHead
        last = first
        cur = pHead
        while cur and cur.next:
            if cur.val != cur.next.val:
                cur = cur.next
                last = last.next
            else:
                val = cur.val
                while cur and cur.val == val:
                    cur = cur.next
                last.next = cur
        return first.next

if __name__ == '__main__':
    result = Solution().deleteDuplication(node1)
    while result:
        print(result.val, end = ' ')
        result = result.next
Donate comment here
------------The End------------
0%