6. 从尾到头打印链表

题目描述

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值。（用数组返回）

Input:
{1, 2, 3}

Output:
[3, 2, 1]

题解

思路1（辅助数组）：
创建辅助数组，从头到尾遍历链表，将节点的值存入辅助数组，最后将辅助数组逆序即可。

时间复杂度O(n)，空间复杂度O(n)

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def print_list_from_tail_to_head(self, head):
        if not head:
            return []
        res = []
        while head:
            res.append(head.val)
            head = head.next
        
        return res[::-1]
    

if __name__ == "__main__":
    head = ListNode(1)
    a = ListNode(2)
    b = ListNode(3)
    head.next = a
    a.next = b
    print(Solution().print_list_from_tail_to_head(head))
    
[3, 2, 1]

思路2（反转链表）：
先将链表反转，然后遍历链表，将节点的值加入数组。

时间复杂度O(n)，空间复杂度O(n)

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def print_list_from_tail_to_head(self, head):
        if not head:
            return []
        cur = head
        pre = None
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        res = []
        point = pre
        while point:
            res.append(point.val)
            point = point.next
        return res
        
    

if __name__ == "__main__":
    head = ListNode(1)
    a = ListNode(2)
    b = ListNode(3)
    head.next = a
    a.next = b
    print(Solution().print_list_from_tail_to_head(head))
[3, 2, 1]

18.1 删除链表节点

题目描述

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点，返回删除后的链表的头节点。

Input:
{2, 5, 1, 9}, 5

Output:
{2, 1, 9}

题解

思路（穿针引线）：
先找到要删除的元素，然后删除点，需要考虑要删除的节点为头节点的特殊情况。

时间复杂度O(n)，空间复杂度O(1)

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def delete_node(self, head, val):
        cur = head
        if cur.val == val:
            return head.next
        while cur and cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            cur = cur.next
        
        return head


if __name__ == "__main__":
    head = ListNode(2)
    a = ListNode(5)
    b = ListNode(1)
    c = ListNode(9)
    head.next = a
    a.next = b
    b.next = c
    val = 5
    cur = Solution().delete_node(head, val)
    while cur:
        print(cur.val)
        cur = cur.next
2
1
9

18.2 删除链表中重复的结点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

Input:
{1, 2, 3, 3, 4, 4, 5}

Output:
{1, 2, 5}

题解

思路1（直接比较删除）：
因为排序的链表中，重复的结点都是连在一起的，因此比较容易找到重复的结点，然后将所有连续相同的结点都跳过，连接不相同的第一个结点。

时间复杂度O(n)，空间复杂度O(1)

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def delete_duplication(self, head):
        if not head:
            return None
        res = ListNode(0)
        res.next = head
        cur = res
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                temp = cur.next.val
                while cur.next and cur.next.val == temp:
                    cur.next = cur.next.next
            else:
                cur = cur.next
                
        return res.next


if __name__ == "__main__":
    head = ListNode(1)
    a = ListNode(2)
    b = ListNode(3)
    c = ListNode(3)
    d = ListNode(4)
    e = ListNode(4)
    f = ListNode(5)
    head.next = a
    a.next = b
    b.next = c
    c.next = d
    d.next = e
    e.next = f
    cur = Solution().delete_duplication(head)
    while cur:
        print(cur.val)
        cur = cur.next
1
2
5

思路2（哈希表）：
使用哈希表辅助统计是否重复。

时间复杂度O(n)，空间复杂度O(n)

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def delete_duplication(self, head):
        if not head:
            return None
        hash_map = dict()
        cur = head
        while cur:
            if cur.val not in hash_map:
                hash_map[cur.val] = 1
            else:
                hash_map[cur.val] += 1
            cur = cur.next
            
        res = ListNode(0)
        res.next = head
        cur = res
        while cur and cur.next:
            if hash_map[cur.next.val] != 1:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return res.next


if __name__ == "__main__":
    head = ListNode(1)
    a = ListNode(2)
    b = ListNode(3)
    c = ListNode(3)
    d = ListNode(4)
    e = ListNode(4)
    f = ListNode(5)
    head.next = a
    a.next = b
    b.next = c
    c.next = d
    d.next = e
    e.next = f
    cur = Solution().delete_duplication(head)
    while cur:
        print(cur.val)
        cur = cur.next
1
2
5

22. 链表中倒数第K个结点

题目描述

输入一个长度为n的链表，返回链表中倒数第k个结点，如果链表长度小于k，则返回None。

Input:
{1, 2, 3, 4, 5}, 2

Output:
{4, 5}

题解

思路（快慢指针）：
创建快慢两个指针，首先快指针先走k步，然后快慢指针同时走，知道快指针走到链表尾部，此时，慢指针指向的就是链表的倒数第k个结点。需要注意的是链表长度小于k时的处理。

时间复杂度O(n)，空间复杂度O(1)

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def find_kth_to_tail(self, head, k):
        fast = head
        slow = head
        for i in range(k):
            if fast:
                fast = fast.next
            else:
                return None
        while fast:
            fast = fast.next
            slow = slow.next
        
        return slow


if __name__ == "__main__":
    head = ListNode(1)
    a = ListNode(2)
    b = ListNode(3)
    c = ListNode(4)
    d = ListNode(5)
    head.next = a
    a.next = b
    b.next = c
    c.next = d
    k = 2
    cur = Solution().find_kth_to_tail(head, k)
    while cur:
        print(cur.val)
        cur = cur.next
4
5

23. 链表中环的入口结点

题目描述

请判断链表是否有环，如果没有则返回None，如果有则返回该链表的环的入口结点。

Input:
{1, 6}, {3, 5, 2, 4}

Output:
3

题解

思路（快慢指针）：
创建快慢两个指针，快指针每次走2步，慢指针每次走1步，当快慢指针相遇且不为空时，说明链表有环。

假设快指针在环中走了n圈，慢指针在环中走了m圈才相遇，且进入环之前的距离为x，环入口到相遇点的距离为y，相遇点到环入口的距离为z，则：

快指针走过的路程=x+n(y+z)+y，慢指针走过的路程=x+m(y+z)+y,而快指针走过的路程=2倍慢指针走过的路程，得到：x=(n-2m)(y+z)-y=(n-2m-1)(y+z)+z.

此时，设置一指针从头出发，每次走一步，另一指针从相遇点出发，每次也走一步，两指针会在环的入口结点相遇。

时间复杂度O(n)，空间复杂度O(1)

快慢指针

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def entry_node_of_loop(self, head):
        fast = head
        slow = head
        while True:
            if not fast or not fast.next:
                return None
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        
        return slow


if __name__ == "__main__":
    head = ListNode(1)
    a = ListNode(6)
    b = ListNode(3)
    c = ListNode(5)
    d = ListNode(2)
    e = ListNode(4)
    head.next = a
    a.next = b
    b.next = c
    c.next = d
    d.next = e
    e.next = b
    cur = Solution().entry_node_of_loop(head)
    print(cur.val)
3

24. 反转链表

题目描述

给定一个单链表的头结点head，长度为n，反转该链表后，返回新链表的表头。

Input:
{2, 1, 5, 3, 4}

Output:
{4, 3, 5, 1, 2}

题解

思路1（迭代）：
设置两个指针，一个指针指向当前结点，一个指针指向当前结点的上一个结点。设置指向上一个结点的指针初始为空。遍历原始链表，每到一个结点，将遇到的结点指针逆向。断掉当前结点向后的指针，改为向前。

时间复杂度O(n)，空间复杂度O(1)

反转链表

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverse_list(self, head):
        if not head or not head.next:
            return head
        pre = None
        cur = head
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        
        return pre


if __name__ == "__main__":
    head = ListNode(2)
    a = ListNode(1)
    b = ListNode(5)
    c = ListNode(3)
    d = ListNode(4)
    head.next = a
    a.next = b
    b.next = c
    c.next = d
    cur = Solution().reverse_list(head)
    while cur:
        print(cur.val)
        cur = cur.next
4
3
5
1
2

题解

思路2（递归）：
对于每个结点，递归向下遍历到最后的尾结点，然后往上依次逆转两个结点，将逆转后的本层结点指向None，返回最底层上来的头部结点。

时间复杂度O(n)，空间复杂度O(n)

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverse_list(self, head):
        if not head or not head.next:
            return head
        temp = head.next
        head.next = None
        new_head = self.reverse_list(temp)
        temp.next = head
        
        return new_head


if __name__ == "__main__":
    head = ListNode(2)
    a = ListNode(1)
    b = ListNode(5)
    c = ListNode(3)
    d = ListNode(4)
    head.next = a
    a.next = b
    b.next = c
    c.next = d
    cur = Solution().reverse_list(head)
    while cur:
        print(cur.val)
        cur = cur.next
4
3
5
1
2

25. 合并两个排序的链表

题目描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的结点仍然是递增的。

Input:
{1, 3, 4, 10, 18}, {2, 3, 7, 8, 9}

Output:
{1, 2, 3, 3, 4, 7, 8, 9, 10, 18}

题解

思路1（双指针迭代）：
定义两个指针分别指向两个链表的头部，比较两个指针指向的结点值，从中取出最小的元素，然后指向最小元素的指针向后走，直到两个指针中任一个走到尾部。最后在将另一个链表的剩余部分全部取出。

时间复杂度O(n)，空间复杂度O(1)

双指针

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def merge(self, head1, head2):
        if not head1:
            return head2
        if not head2:
            return head1
        p = ListNode(-1)
        q = p
        while head1 and head2:
            if head1.val < head2.val:
                p.next = head1
                head1 = head1.next
            else:
                p.next = head2
                head2 = head2.next
            p = p.next
        if head1:
            p.next = head1
        if head2:
            p.next = head2
        
        return q.next


if __name__ == "__main__":
    head1 = ListNode(1)
    a = ListNode(3)
    b = ListNode(4)
    c = ListNode(10)
    d = ListNode(18)
    head1.next = a
    a.next = b
    b.next = c
    c.next = d
    
    head2 = ListNode(2)
    e = ListNode(3)
    f = ListNode(7)
    g = ListNode(8)
    h = ListNode(9)
    head2.next = e
    e.next = f
    f.next = g
    g.next = h
    
    cur = Solution().merge(head1, head2)
    while cur:
        print(cur.val)
        cur = cur.next
1
2
3
3
4
7
8
9
10
18

题解

思路2（双指针递归）：
每次比较两个链表当前结点的值，然后取较小值的链表指针往后，另一个不变，两段子链表作为新的链表送入递归中，递归回来的结果加在较小值的结点的后面，当两个链表有一个为空时，递归终止。

时间复杂度O(n)，空间复杂度O(n)

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def merge(self, head1, head2):
        if not head1:
            return head2
        if not head2:
            return head1
        if head1.val < head2.val:
            head1.next = self.merge(head1.next, head2)
            return head1
        else:
            head2.next = self.merge(head1, head2.next)
            return head2


if __name__ == "__main__":
    head1 = ListNode(1)
    a = ListNode(3)
    b = ListNode(4)
    c = ListNode(10)
    d = ListNode(18)
    head1.next = a
    a.next = b
    b.next = c
    c.next = d
    
    head2 = ListNode(2)
    e = ListNode(3)
    f = ListNode(7)
    g = ListNode(8)
    h = ListNode(9)
    head2.next = e
    e.next = f
    f.next = g
    g.next = h
    
    cur = Solution().merge(head1, head2)
    while cur:
        print(cur.val)
        cur = cur.next
1
2
3
3
4
7
8
9
10
18

35. 复杂链表的复制

题目描述

输入一个复杂链表（每个结点中有节点值，以及两个指针，一个指向下一个结点，另一个特殊指针random指向一个随机结点，请对此链表进行深拷贝，并返回拷贝后的头结点。

Input:
{1, 2, 3, 3, 1, 1}

Output:
{1, 2, 3, 3, 1, 1}

题解

思路（双指针）：
先遍历链表，对每个结点新建一个拷贝结点，并插入到该结点之后，然后使用双指针再次遍历链表，两个指针每次都一共两步，一个指针遍历原始结点，另一个指针遍历拷贝结点，拷贝结点的随机指针跟随原始结点，指向原始结点随机指针的下一位。最后再次使用双指针遍历链表，每次越过后一位相连，即拆分为两个链表。

时间复杂度O(n)，空间复杂度O(1)

双指针

class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None

class Solution:
    def clone(self, head):
        if not head:
            return head
        cur = head
        while cur:
            clone = RandomListNode(cur.label)
            clone.next = cur.next
            cur.next = clone
            cur = clone.next
        cur = head
        clone = head.next
        res = head.next
        while cur:
            if not cur.random:
                clone.random = None
            else:
                clone.random = cur.random.next
            cur = cur.next.next
            if clone.next:
                clone = clone.next.next
        cur = head
        clone = head.next
        while cur:
            cur.next = cur.next.next
            cur = cur.next
            if clone.next:
                clone.next = clone.next.next
            clone = clone.next
            
        return res

if __name__ == "__main__":
    head = RandomListNode(1)
    a = RandomListNode(2)
    b = RandomListNode(3)
    head.next = a
    a.next = b
    head.random = b
    a.random = head
    b.ramdom = head
    
    
    p = Solution().clone(head)
    cur = p
    while cur:
        print(cur.label)
        cur = cur.next
    while p:
        if p.random:
            print(p.random.label)
        p = p.next
1
2
3
3
1

52. 两个链表的第一个公共结点

题目描述

输入两个无环的单向链表，找出他们的第一个公共结点，如果没有公共节点则返回空。

Input:
{1,2,3},{4,5},{6,7}

Output:
{6, 7}

题解

思路（双指针法）：
创建两个指针分别指向两链表的初始结点，然后让指针A遍历链表1，让指针B遍历链表2，当指针A和指针B都遍历完各自的节点后，让指针A遍历链表2，让指针B遍历链表1，直到两个指针指向的结点先相等。

时间复杂度O(m+n)，空间复杂度O(1)

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def find_first_common_node(self, head1, head2):
        if not head1 or not head2:
            return None
        p, q = head1, head2
        while p != q:
            p = p.next if p else head2
            q = q.next if q else head1
        
        return p


if __name__ == "__main__":
    head1 = ListNode(1)
    a = ListNode(2)
    b = ListNode(3)
    head1.next = a
    a.next = b
    head2 = ListNode(4)
    c = ListNode(5)
    head2.next = c
    e = ListNode(6)
    f = ListNode(7)
    b.next = e
    e.next = f
    c.next = e
    
    
    cur = Solution().find_first_common_node(head1, head2)
    while cur:
        print(cur.val)
        cur = cur.next
6
7

参考文章

本文是笔者通过下列网站学习的记录，有部分修改和补充，转载请注明出处，并附带下面链接。

  1. 【CS-Notes剑指Offer题解】
  2. 【牛客网剑指Offer】