链表

发表于 | 分类于 ， | 评论数：

从头到尾打印链表

题目

输入一个链表，返回一个反序的链表

思路

通常，这种情况下，我们不希望修改原链表的结构。返回一个反序的链表，这就是经典的“后进先出”，我们可以使用栈实现这种顺序。每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，给一个新的链表结构，这样链表就实现了反转。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        result = []
        while listNode:
            result.insert(0, listNode.val)
            listNode = listNode.next
        return result

链表中倒数第K个节点

题目

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

思路

我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if not head or k == 0:
            return None
        before_node = head
        after_node = None
        search_times = 0
        while before_node:
            search_times += 1
            before_node = before_node.next
            if search_times == k:
                after_node = head
            elif search_times > k:
                after_node = after_node.next
        return after_node

反转链表

题目

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

思路

这个很简单，我们使用三个指针，分别指向当前遍历到的结点、它的前一个结点以及后一个结点。

在遍历的时候，做当前结点的尾结点和前一个结点的替换。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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
        last = None
        while pHead:
            tmp = pHead.next
            pHead.next = last
            last = pHead
            pHead = tmp
        return last

合并两个排序链表

题目

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

思路

先判断输入的链表是否为空的指针。
如果第一个链表为空，则直接返回第二个链表；
如果第二个链表为空，则直接返回第一个链表。
如果两个链表都是空链表，合并的结果是得到一个空链表。

两个链表都是排序好的，我们只需要从头遍历链表，判断当前指针，哪个链表中的值小，即赋给合并链表指针即可。
使用递归就可以轻松实现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#使用递归就可以轻松实现。
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        if pHead1.val < pHead2.val:
            pHead1.next = self.Merge(pHead1.next, pHead2)
            return pHead1
        else:
            pHead2.next = self.Merge(pHead1, pHead2.next)
            return pHead2

复杂链表的复制

题目

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路

我们这里采用三步：
第一步：复制复杂指针的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
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        if not pHead:
            return None
         
        dummy = pHead
         
        # first step, N' to N next
        while dummy:
            dummynext = dummy.next
            copynode = RandomListNode(dummy.label)
            copynode.next = dummynext
            dummy.next = copynode
            dummy = dummynext
         
        dummy = pHead
         
        # second step, random' to random'
        while dummy:
            dummyrandom = dummy.random
            copynode = dummy.next
            if dummyrandom:
                copynode.random = dummyrandom.next
            dummy = copynode.next
         
        # third step, split linked list
        dummy = pHead
        copyHead = pHead.next
        while dummy:
            copyNode = dummy.next
            dummynext = copyNode.next
            dummy.next = dummynext
            if dummynext:
                copyNode.next = dummynext.next
            else:
                copyNode.next = None
            dummy = dummynext
 
        return copyHead

两个链表的第一个公共节点

题目

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

思路

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if pHead1 == None or pHead2 == None:
            return None
        cur1, cur2 = pHead1, pHead2
        while cur1 != cur2:
            cur1 = cur1.next if cur1 != None else pHead2
            cur2 = cur2.next if cur2 != None else pHead1
        return cur1

链表中环的入口节点

题目

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

思路

可以用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头结点。
如果链表中的环有n个结点，指针P1先在链表上向前移动n步，然后两个指针以相同的速度向前移动。
当第二个指针指向的入口结点时，第一个指针已经围绕着揍了一圈又回到了入口结点。
以下图为例，指针P1和P2在初始化时都指向链表的头结点。由于环中有4个结点，指针P1先在链表上向前移动4步。
接下来两个指针以相同的速度在链表上向前移动，直到它们相遇。它们相遇的结点正好是环的入口结点。

现在，关键问题在于怎么知道环中有几个结点呢？
可以使用快慢指针，一个每次走一步，一个每次走两步。如果两个指针相遇，表明链表中存在环，
并且两个指针相遇的结点一定在环中。 随后，我们就从相遇的这个环中结点出发，
一边继续向前移动一边计数，当再次回到这个结点时，就可以得到环中结点数目了。

代码

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
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead == None:
            return None
        # 判断环是否存在，并找到一个存在于环内的节点
        meetingnode = self.MeetingNode(pHead)
        if meetingnode == None:
            return None
        # 通过将节点在环内遍历一次，确定环的长度
        nodeslop = 1
        node1 = meetingnode
        while node1.next != meetingnode:
            node1 = node1.next
            nodeslop += 1
        
        # 找到距离头部节点环长度的节点
        node1 = pHead
        for _ in range(nodeslop):
            node1 = node1.next
        
        # 设置一个后来节点，和上一个节点一起遍历，当他们相遇的时候，就是节点的入口
        node2 = pHead
        while node1 != node2:
            node1 = node1.next
            node2 = node2.next
        return node1
    
    # 先找到快慢节点相遇的节点， 存在的节点就处在环内
    def MeetingNode(self, pHead):
        slow = pHead.next  # 慢指针
        if slow == None:
            return None
        fast = slow.next   # 快指针
        while fast != None and slow != None:  # 任意一个指针为Nonde 说明不存在环
            # 快慢节点相遇，找到存在于环内的节点
            if slow == fast:
                return fast
            slow = slow.next
            fast = fast.next
            if fast != None:
                fast = fast.next
        return None

删除链表中重复节点

题目

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

思路

删除重复结点，只需要记录当前结点前的最晚访问过的不重复结点pPre、当前结点pCur、指向当前结点后面的结点pNext的三个指针即可。
如果当前节点和它后面的几个结点数值相同，那么这些结点都要被剔除，然后更新pPre和pCur；如果不相同，则直接更新pPre和pCur。

需要考虑的是，如果第一个结点是重复结点我们该怎么办？这里我们分别处理一下就好，如果第一个结点是重复结点，那么就把头指针pHead也更新一下。

代码

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

class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        pPre = None   # 记录前一个加点的指针，用来将新的不重复节点放到其后面
        pCur = pHead  # 记录当前处理的节点
        while pCur != None:
            # 如果下一个几点不是None， 并且下一个节点的数据和当前节点数据相等
            if pCur.next != None and pCur.val == pCur.next.val:
                pNext = pCur.next
                # 往下寻找不相等的节点
                while pNext.next != None and pNext.next.val == pCur.val:
                    pNext = pNext.next
                # 如果当前节点是头结点，将pNext.next 赋值给pHead
                if pCur == pHead:
                    pHead = pNext.next
                # 否则将pNext.next 赋值给pPre.next
                else:
                    pPre.next = pNext.next
                pCur = pNext.next
            else:
                pPre = pCur
                pCur = pCur.next
        return pHead
刘小恺(Kyle) wechat
如有疑问可联系博主