面试必刷TOP101：链表（11-16，Python实现）

11.两个链表生成相加列表（小试牛刀）

11.1 反转链表法

class Solution:
    def ReverseList(self, pHead: ListNode) -> ListNode:
        if pHead == None:
            return None
        cur = pHead
        pre = None
        while cur != None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        if head1 == None:
            return head2
        if head2 == None:
            return head1
        head1 = self.ReverseList(head1)
        head2 = self.ReverseList(head2)
        res = ListNode(-1)
        head = res
        carry = 0
        while head1 != None or head2 != None or carry != 0:
            val1 = 0 if head1 == None else head1.val
            val2 = 0 if head2 == None else head2.val
            temp = val1 + val2 + carry
            carry = int(temp / 10)
            temp = temp % 10
            head.next = ListNode(temp)
            head = head.next
            if head1 != None:
                head1 = head1.next
            if head2 != None:
                head2 = head2.next
        return self.ReverseList(res.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

时间复杂度：O(max(m,n))，其中 m 与 n 分别为两个链表的长度，翻转链表三次，复杂度分别是 O(n)、O(m)、O(max(m,n))，相加过程也是遍历较长的链表。
空间复杂度：O(1)，常数级指针，没有额外辅助空间，返回的新链表属于必要空间。

12.单链表的排序（小试牛刀）

12.1 归并排序法

class Solution:
    def merge(self, pHead1: ListNode, pHead2: ListNode) -> ListNode:
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        head = ListNode(-1)
        cur = head
        while pHead1 != None and pHead2 != None:
            if pHead1.val <= pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            cur = cur.next
        if pHead1 != None:
            cur.next = pHead1
        if pHead2 != None:
            cur.next = pHead2
        return head.next
    def sortInList(self , head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        left = head
        mid = head.next
        right = head.next.next
        while right != None and right.next != None:
            left = left.next
            mid = mid.next
            right = right.next.next
        left.next = None
        return self.merge(self.sortInList(head),self.sortInList(mid))
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

时间复杂度：O(nlogn)，归并排序的复杂度。
空间复杂度：O(logn)，递归栈的深度最坏为 logn 层。

12.2 转为数组排序法

class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        a = []
        p = head
        while p != None:
            a.append(p.val)
            p = p.next
        p = head
        a = sorted(a)
        for i in range(0,len(a)):
            p.val = a[i]
            p =p.next
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(nlogn)，sort 函数的复杂度
空间复杂度：O(n)，存储链表元素值的辅助数组长度 n

13.判断一个链表是否为回文结构（小试牛刀）

13.1 数组复制反转法

class Solution:
    def isPail(self , head: ListNode) -> bool:
        a = []
        while head != None:
            a.append(head.val)
            head = head.next
        b = a.copy()
        b.reverse()
        for i in range(0,len(a)):
            if a[i] != b[i]:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：O(n)，其中 n 为链表的长度，遍历链表转化数组为 O(n)，反转数组为 O(n)，后续遍历两个数组为 O(n）。
空间复杂度：O(n)，记录链表元素的辅助数组。

13.2 数组复制双指针

class Solution:
    def isPail(self , head: ListNode) -> bool:
        a = []
        while head != None:
            a.append(head.val)
            head = head.next
        left = 0
        right = len(a) - 1
        while left <= right:
            if a[left] != a[right]:
                return False
            left = left + 1
            right = right - 1
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：O(n)，其中 n 为链表的长度，遍历链表转化数组为 O(n)，双指针遍历半个数组为 O(n)。
空间复杂度：O(n)，记录链表元素的辅助数组。

13.3 长度法找中点

class Solution:
    def reverse(self, head: ListNode):
        p = None
        while head != None:
            temp = head.next
            head.next = p
            p = head
            head = temp
        return p
    def isPail(self , head: ListNode) -> bool:
        p = head
        n = 0
        while p != None:
            n = n + 1
            p = p.next
        n = n / 2
        p = head
        while n > 0:
            p = p.next
            n = n - 1
        p = self.reverse(p)
        q = head
        while p != None:
            if p.val != q.val:
                return False
            p = p.next
            q = q.next
        return True
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

时间复杂度：O(n)，其中 n 为链表的长度，遍历链表找到长度为 O(n)，后续反转链表为 O(n)，然后再遍历两份半个链表。
空间复杂度：O(1)，常数级变量，没有额外辅助空间。

13.4 双指针找中点

class Solution:
    def reverse(self, head: ListNode):
        p = None
        while head != None:
            temp = head.next
            head.next = p
            p = head
            head = temp
        return p
    def isPail(self , head: ListNode) -> bool:
        if head == None:
            return True
        p = head
        q = head
        while p != None and p.next != None:
            p = p.next.next
            q = q.next
        q = self.reverse(q)
        p = head
        while q != None:
            if p.val != q.val:
                return False
            p = p.next
            q = q.next
        return True
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

时间复杂度：O(n)，其中 n 为链表的长度，双指针找到中点遍历半个链表，后续反转链表为 O(n)，然后再遍历两份半个链表。
空间复杂度：O(1)，常数级变量，没有额外辅助空间。

13.5 栈逆序

class Solution:
    def isPail(self , head: ListNode) -> bool:
        p = head
        a = []
        while p:
            a.append(p.val)
            p = p.next
        p = head
        while len(a) != 0:
            if p.val != a.pop():
                return False
            p = p.next
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(n)，其中 n 为链表的长度，遍历链表入栈为 O(n)，后续再次遍历链表和栈。
空间复杂度：O(n)，记录链表元素的辅助栈。

14.链表的奇偶重排（小试牛刀）

14.1 奇偶重排

class Solution:
    def oddEvenList(self , head: ListNode) -> ListNode:
        if head == None:
            return head
        p = head
        q = head.next
        res = q
        while q != None and q.next != None:
            p.next = q.next
            p = p.next
            q.next = q.next.next
            q = q.next
        p.next = res
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：O(n)，遍历一次链表。
空间复杂度：O(1)，常数个指针，无额外辅助空间。

15.删除有序链表中重复的结构（一）（小试牛刀）

15.1 遍历删除

class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        if head == None:
            return None
        p = head
        while p != None and p.next != None:
            if p.val == p.next.val:
                p.next = p.next.next
            else:
                p = p.next
        return head
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：O(n)，其中 n 为链表长度，遍历一次链表。
空间复杂度：O(1)，没有使用额外的辅助空间。

16.删除有序链表中重复的结构（二）（小试牛刀）

16.1 直接比较删除法

class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        if head == None:
            return None
        res = ListNode(-1)
        res.next = head
        p = res
        while p.next != None and p.next.next != None:
            if p.next.val == p.next.next.val:
                temp = p.next.val
                while p.next != None and p.next.val == temp:
                    p.next = p.next.next
            else:
                p = p.next
        return res.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：O(n)，其中 n 为链表结点数，只有一次遍历。
空间复杂度：O(1)，只开辟了临时指针，没有额外空间。

16.2 哈希表

class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        if head == None:
            return None
        p = head
        a = dict()
        while p != None:
            if p.val in a:
                a[p.val] += 1
            else:
                a[p.val] = 1
            p = p.next
        res = ListNode(-1)
        res.next = head
        p = res
        while p.next != None:
            if a[p.next.val] != 1:
                p.next = p.next.next
            else:
                p = p.next
        return res.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：O(n)，其中 n 为链表结点数，一共两次遍历，每次计数、每次查询都是 O(1)
空间复杂度：O(n)，最坏情况下 n 个结点都不相同，哈希表长度为 n