chapter14-linkedList-algorithm

Posted on | In | | Visitors: ℃
Words count in article: 1.8k | Reading time ≈ 8

chapter14-linkedList-algorithm

[TOC]

链表类算法
1. 找出两个链表的交点

Leetcode / 力扣

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # you题意可知
        # 两个链表相交，结果有两种
        # 1. 只相交一点，后面的链表完全不同
        # 2. 相交一点后，后面的链表完全相同(如果后面只有两点相同，后面不同，那么一个点是需要两个next的，这是不符合链表规则的)
        # 因此解法如下：
        # 1. 把两链表结果相连，判断最后一个元素相同，或者是否有环
        # 2. 不相连，分别遍历两次headA和headB并且交替遍历，这样总会有一个值相等，要么交点，要么结尾
        # 因为 a + b = b + a
        # 因此代码逻辑如下：
        l1, l2 = headA, headB
        while(l1 != l2):
            if not l1:
                l1 = headB
            else:
                l1 = l1.next
            if not l2:
                l2 = headA
            else:
                l2 = l2.next
        print(l1)
        return l1


headA = ListNode(4)
headB = ListNode(4)
headC = ListNode(4)
headA.next = headC
headB.next = headC
s = Solution()
s.getIntersectionNode(headA = headA, headB = headB)
2. 链表反转

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution2:
    # 递归
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head # 返回最后一个结点给NewHead，作为头结点
        node = head.next
        newHead = self.reverseList(node)
        node.next = head # 利用当前节点node的值，去指向返回的倒数第二个值，就实现了反转，然后依次返回，反转
        head.next = None # node为当前链表，原链表就需要断开以前的值，只需要当前节点
        return newHead
    # 头插法
    def reverseList2( self, head: ListNode ) -> ListNode:
        # 新拟一个头结点
        newHead = ListNode(-1)
        while head:
            node = head.next # 为了移动节点
            head.next = newHead.next # 断开指向一个的next，转向-1(newHead)只指向的下一个
            newHead.next = head # 把-1(newHead)指向的值，指向到head，就实现了吧当前值插入到-1(newHead)的后面
            head = node # 更新到下一个节点
        return newHead.next
3. 归并两个有序的链表

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution3:
    # you题意可知
    # 归并两个有序的链表
    # 根据判断大小依次往下递归
    # 难点就在于如果有一个遍历完了，说明后面的数，只需要连接再后面即可，因为后面的数一定比前面的数都大，不需要在比较了
    # 而不知道那一个先遍历完，所以都要根据大小分别遍历
    # 而先遍历玩的一边，全部点也返回到先遍历完的一边进行连接返回即可
    # 代码逻辑如下：
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l2.next, l1)
            return l2
l1 = ListNode(4)
l1.next = ListNode(5)
l2 = ListNode(4)
s = Solution3()
s.mergeTwoLists(l1, l2)
4. 从有序链表中删除重复节点

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution4:

    # 又题意可知
    # 深度遍历链表
    # 如果返回值是，当前值和前一个值相同就返回前一个值（这样就删除了相同的值）
    # 如果不同就返回当前值
    # 逻辑代码如下：
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        newHead = head.next
        head.next = self.deleteDuplicates(newHead)
        if newHead.val == head.val:
            return head.next
        else:
            return head
5. 删除链表的倒数第 n 个节点

Leetcode / 力扣

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
def removeNthFromEnd(head: ListNode, n: int):
    # you题意可知
    # 删除链表节点，必须先知道删除节点的前一个节点
    # 由于是删除倒数第n个节点
    # 使用快慢指针的方法即可找到删除最后一个节点
    # 意为，快指针先移动n个结点，然后慢指针从头结点遍历，
    # 快指针的下一个节点为空是，那么慢指针就找到删除节点的前一个节点了
    # 先保留下一个节点，然后删除，并且释放空间即可
    # 代码逻辑如下：
    fast = head
    while n:
        fast = fast.next
        n -= 1
    if not fast:
        return head.next
    slow = head
    while fast.next:
        fast = fast.next
        slow = slow.next
    dNode = slow.next
    slow.next = slow.next.next
    del dNode
    return head

l1 = ListNode(4)
l1.next = ListNode(5)
removeNthFromEnd(l1, 1)
6. 交换链表中的相邻结点

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 24. 两两交换链表中的节点
def swapPairs(head: ListNode) -> ListNode:
    node = ListNode(-1)
    node.next = head
    pre = node
    while pre.next and pre.next.next:
        l1, l2 = pre.next, pre.next.next
        next = l2.next
        l1.next = next
        l2.next = l1
        pre.next = l2

        pre = l1

    return node.next

l1 = ListNode(4)
l1.next = ListNode(5)
swapPairs(l1)
7. 链表求和

Leetcode / 力扣

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
def addTwoNumbers(l1: ListNode, l2: ListNode):
    # you题意可知
    # 直接把链表数据转为数组或者直接数字
    # 然后相加后，直接通过取数，创建链表即可
    # 代码逻辑如下：
    def buildStack( root ):
        stack = [ ]
        while (root):
            stack.append(root.val)
            root = root.next
        return stack

    ls1 = buildStack(l1)
    ls2 = buildStack(l2)

    carry = 0
    root = ListNode(-1)
    while carry or ls1 or ls2:
        vs1 = ls1.pop() if ls1 else 0
        vs2 = ls2.pop() if ls2 else 0
        s = vs1 + vs2 + carry
        node = ListNode(s % 10)
        node.next = root.next
        root.next = node

        carry = s // 10
    return root.next
# l1 = ListNode(4)
# l1.next = ListNode(5)
# l2 = ListNode(4)
# l2.next = ListNode(5)
# addTwoNumbers(l1, l2)
8. 回文链表

Leetcode / 力扣

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
def isPalindrome(head: ListNode) -> bool:
    # 有题意可知
    # 找到链表终点，反转后面链表，判断反转后的链表与前面的链表是否一致
    # 代码逻辑如下

    # 如果为空，则为真
    if not head or not head.next:
        return True
        # 找到用户终点指针

    # 找到链表终点，并且切断终点链表之间相互的连接
    def findMidLinkNode( root ):
        slow, fast = root, root
        pre = slow
        while (fast.next and fast.next.next):
            pre = slow
            slow = slow.next
            fast = fast.next.next

        # 如果链表为偶数，则终点链表，指向下一个节点
        if fast.next:
            slow = slow.next
            pre = pre.next
        # 断开head
        pre.next = None
        return slow

    # 反转后面部分的指针
    def reverseLinklist( root ):
        RN = ListNode(-1)

        while (root):
            next = root.next
            root.next = RN.next
            RN.next = root
            root = next

        return RN.next

    # 输出链表
    def printL( l ):
        r = [ ]
        while (l):
            r.append(l.val)
            l = l.next
        print(r)

    MNode = findMidLinkNode(head)
    printL(MNode)
    MNode = reverseLinklist(MNode)
    printL(MNode)

    # 判断是否为回文链表
    while head and MNode:
        if head.val != MNode.val:
            return False
        head, MNode = head.next, MNode.next

    return True

l1 = ListNode(4)
l1.next = ListNode(5)
# l1.next.next = ListNode(2)
# l1.next.next.next = ListNode(4)
print(isPalindrome(l1))
9. 分隔链表

Leetcode / 力扣

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
def splitListToParts(root, k):

    # you题意可知
    # 通过求链表长度n
    # 由k段，有与要分段基本相同，由于可能是有余数的
    # 所以对n进行求n//k and n%k 得到倍数和余数
    # 然后通过remainder的变化进行遍历，分割链表即可
    n = 0
    curr = root
    while curr:
        curr = curr.next
        n += 1
    # 算出倍数以及余数 // %
    width, remainder = divmod(n, k)

    result = [ ]
    curr = root
    for i in range(k):
        head = curr
        # 难点在这，遍历width-1次，通过余数remainder进行判断是否全长度遍历
        for j in range(width - 1 + int(i < remainder)):
            if curr:
                curr = curr.next
        if curr:
            curr.next, curr = None, curr.next
        result.append(head)
    return result
10. 链表元素按奇偶聚集

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def oddEvenList(head: ListNode ) -> ListNode:
    # 取出奇偶数，为两个链表
    # 最后相连即可
    # 代码逻辑如下：

    if not head:
        return head

    odd, even, evenhead = head, head.next, head.next
    while even and even.next:
        odd.next = odd.next.next
        odd = odd.next
        even.next = even.next.next
        even = even.next
    odd.next = evenhead
    return head
11. 移除链表元素

力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def removeElements(self, head: ListNode, val: int) -> ListNode:
    dummy = ListNode(float("-inf"))
    dummy.next = head
    prev, curr = dummy, dummy.next

    while curr:
        if curr.val == val:
            prev.next = curr.next
        else:
            prev = curr

        curr = curr.next

    return dummy.next