当前位置:   article > 正文

力扣练习4.25_力扣 训练

力扣 训练

92. 反转链表 II

要求在指定的区间内反转。
解题思路:
将整个链表拆成三部分,第一部分是头节点到left的前一个节点,第二部分是left到right的待反转区间,第三部分是right的下一个节点为头结点到尾部。
首先根据反转链表的方法遍历待反转区间的链表,不断修改每个节点的指向。
然后将反转的链表的首尾和第一、三个部分相连接。

步骤:
1.初始化哑结点,将其指向头结点,设置前驱节点,初始化为pre,指向哑结点
2.遍历链表,直到遍历到left的前一个节点,保存为pre
3.设置反转区间的遍历反转变量:前驱节点:start=pre.next;指针节点:cur=start.next
4.在指定区间内反转:根据反转链表的方法
5.此时的start移动到了待反转链表的尾部,反转完成后就是头节点位置;cur移动到了第三部分的头结点;反转完成后的尾部就是待反转链表的头节点,也就是pre.next,这个指针是没有变的。
6.先链接反转链表和第三个区间:将反转完成后的尾部的指针指向第三部分的头结点——pre.next.next = cur
7.链接第一个区间和反转链表:left的前一个节点(第一个区间的尾部)指向反转链表的头结点——pre.next = start
8.返回头结点,是哑结点指向的节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:

        # 创建哑节点
        dummy_node = ListNode(-1)
        dummy_node.next =head
        # 设置前驱节点
        pre = dummy_node

        # 遍历到左界的前一个节点
        for _ in range(left-1):
            pre = pre.next
        
        # 初始化遍历反转的前驱和指针节点
        start = pre.next
        cur = start.next

        # 在指定区间内反转链表
        for _ in range(right-left):
            temp = cur.next # 临时变量存储指针节点的后继节点
            cur.next = start # 修改指针节点的指向,指向前驱节点
            start = cur # 将前驱节点修改为指针节点
            cur = temp # 将指针节点移动到其后继节点
        
        # 拼接三个区间
        # 这个时候,pre仍指向反转区间的第一个节点,该节点,也就是pre.next已成为为反转区间的尾部
        # 尾部应该链接cur,因为不断反转后cur指针的位置是在第三个区间的头节点
        pre.next.next = cur # 完成反转区间和第三个区间的链接
        # 第二个和第三个区间链接了,现在链接第一个和第二个
        # 此时的start移动到了反转后链表的头节点,更新第一个区间的尾部节点的指针
        pre.next = start

        return dummy_node.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
  • 36
  • 37
  • 38
  • 39

234. 回文链表

解题思路一

将链表的值复制到数组,数组和其逆序比较,相同即为回文。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 遍历,形成list,反转list,看两者是否相同
        list_1 = [] # 正序
        cur = head
        while cur:
            list_1.append(cur.val)
            cur = cur.next
        
        if list_1 == list_1[::-1]:
            return True
        else:
            return False

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

解题思路二

链表的方式。找到链表的中点;将链表的中点及之后的子链表反转;逐个比较同位置的节点值。
步骤:
1.设置快慢指针,都从头节点开始,快指针一次移动两个单位,慢指针一个单位,当快指针移动到链表末尾时,慢指针位置就是中点。(奇数个节点时是中点,偶数个是中间俩节点的右节点)
2.从中点开始反转,是包括中点的。得到反转后的头节点。
3.以反转后的子链表为基准,和原始链表从头节点开始比较值,全部相同即为回文。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 找中点
        slow, fast = head,head
        # 遍历,慢指针移动一步,快指针移动两步,循环退出后slow就在中点
        # 中点被包含在后半部分
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 反转链表函数,默认操作,返回反转后的头结点pre,cur是下一个区间的头节点
        def reverse(head):
            # 前驱节点
            pre = None
            cur = head
            while cur:
                temp = cur.next
                cur.next = pre
                pre = cur
                cur = temp
            return pre # 返回反转部分的头节点
        # 反转中点及之后的链表
        reversed_list = reverse(slow)
        
        # 比较原始的链表和反转后的子链表
        first_list = head
        flag = True
        # 以反转后的子链表为基线
        while reversed_list:
            # 比较同一位置的值
            if reversed_list.val != first_list.val:
                flag = False
                break
            # 同时往后移动
            reversed_list = reversed_list.next
            first_list = first_list.next
        # 返回结果
        return flag

  • 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

21. 合并两个有序链表

解题思路:逐步比较两个链表的节点,将较小的节点依次添加进新链表。
步骤:
1.新建哑结点,指针节点指向它。
2.设置循环,直到某一个链表被遍历完。
3.循环体内判断两个链表此时的头节点的大小,将小的节点加到指针节点后面(加在新链表后面)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 哑结点
        dummy_node = ListNode(-1)
        # 指针节点
        cur = dummy_node
        # 遍历两个链表,当某一个被遍历完成后退出
        while list1 and list2:
            # 根据大小排序
            if list1.val > list2.val:
                # 将新链表的头节点指向较小的节点
                cur.next = list2
                # 移动较小的节点的头节点
                list2 = list2.next
            else:
                # 将新链表的头节点指向较小的节点
                cur.next = list1
                # 移动较小的节点的头节点
                list1 = list1.next
            # 移动指针节点
            cur = cur.next
        # 退出后检查某一个链表还没遍历完
        if list1: # list1没有遍历完,直接将新链表的尾节点指向剩余的list1
            cur.next = list1
        if list2: # 同理
            cur.next = list2
        # 返回新建链表的头节点
        return dummy_node.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

148. 排序链表

解题思路:

将链表复制为数组,sort后转为链表。(错误)

从链表的角度考虑,最适合排序的算法就是归并排序。分割+合并。
链表的分割也是找中点,前面的题有过,与前面不同的是,这道题的中点是要包含在前面部分的,所以初始化fast不同;
链表的合并:上一题直接拿过来;
最后弄个主函数将其组合起来,递归进行,每次都找中点,分割出左右子链表,排序,合并。

步骤

1.将以上思路包装为不同的函数
2.找中点函数:fast初始化为fast.next
3.合并有序链表函数
4.主函数:找到中点,趁还没断链,先用mid.next作为右子链表的头节点排序右子链表;断链后对左子链表排序,都是递归进行;最后返回对排序后的链表的归并结果。终止条件是只有一个节点。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        # 找到中点的函数
        def get_mid(head):
            if not head: return head
            # fast初始化为head.next,使得在偶数情况下循环完成后slow处于中间两个节点靠左
            slow, fast = head, head.next
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        
        # 有序合并链表的函数(升序)
        def merge(l1,l2):
            dummy_node = ListNode(-1)
            cur = dummy_node
            # 当两个链表有一个遍历完成,就退出
            while l1 and l2:
                if l1.val > l2.val:
                    cur.next = l2
                    l2 = l2.next
                else:
                    cur.next = l1
                    l1 = l1.next
                cur = cur.next
            
            # 还有剩余的
            if l1:
                cur.next = l1
            if l2:
                cur.next = l2

            return dummy_node.next

        # 主函数,归并排序
        def merge_sort(head):
            # 递归出口,没有节点或者只有一个节点,返回自身
            if not head or not head.next:
                return head
            # 获取中点
            mid = get_mid(head)
            # 对右子链表排序(递归),mid是要算在左边的,防止只有两个节点的情况
            right_sorted = merge_sort(mid.next)
            # 中点断开,获得左子链表,排序
            mid.next = None
            left_sorted = merge_sort(head)
            # 最开始两个子链表分别只有一个元素,逐渐增加也是有序的,转换为合并有序链表
            return merge(left_sorted, right_sorted)
        
        # 启动排序
        return merge_sort(head)


  • 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

23. 合并 K 个升序链表

解题思路一

最直观的思路就是以第一个链表为基准,后面的不停的与其合并。
转换为了合并两个有序链表的问题。但是时间复杂度是 O(kN),其中 k 是链表的数量,N 是链表中的节点总数。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        if len(lists)==1:
            return lists[0]

        # 合并两个链表
        def merge(l1,l2):
            dummy_node = ListNode(-1)
            cur = dummy_node
            while l1 and l2:
                if l1.val > l2.val:
                    cur.next = l2
                    l2 = l2.next
                else:
                    cur.next = l1
                    l1 = l1.next
                cur = cur.next
            if l1:
                cur.next = l1
            if l2:
                cur.next = l2
            return dummy_node.next
        

        # 初始化,以第一个链表为基准
        sort_list = lists[0]
        for i in range(1, len(lists)):
            sort_list = merge(sort_list, lists[i])

        return sort_list


  • 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

解题思路二

分治法,找到中点,区分左右列表,排序。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        if len(lists)==1:
            return lists[0]

        # 合并两个链表
        def merge(l1,l2):
            dummy_node = ListNode(-1)
            cur = dummy_node
            while l1 and l2:
                if l1.val > l2.val:
                    cur.next = l2
                    l2 = l2.next
                else:
                    cur.next = l1
                    l1 = l1.next
                cur = cur.next
            
            cur.next = l1 or l2
            return dummy_node.next
        
        # 分治法
        # 找中点,区分左右
        mid = len(lists)//2
        # 递归调用自身
        left_list = self.mergeKLists(lists[:mid])
        right_list = self.mergeKLists(lists[mid:])

        return merge(left_list, right_list)
  • 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

解题思路三

最小堆(优先队列)
定义最小堆,初始化为每个链表的头节点,不断将堆顶元素出堆,添加到结果链表中。

步骤:

1.导入heapq模块实现最小堆
2.初始化最小堆,添加每个链表的头节点,包括值、索引、节点本身
3.创建哑结点,作为结果链表的开始
4.当堆不为空,将堆顶元素出堆,添加到结果链表后面
5.如果堆顶元素后面还有值,继续将其入堆
6.返回哑结点.next即为结果链表头节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 处理为空情况
        if not lists: return None

        # 定义最小堆
        heaq = []
        # 初始化最小堆,将每个链表的首个节点加入堆
        for index, node in enumerate(lists):
            if node:
                # 将节点值、索引、节点本身入堆
                heapq.heappush(heaq, (node.val, index, node))
            
        # 创建新链表的开始,哑结点
        dummy = ListNode(-1)
        cur = dummy

        # 当最小堆不为空
        while heaq:
            # 从最小堆中弹出最小元素(升序)
            val, idx, node = heapq.heappop(heaq)
            # 创建新的节点,添加到结果链表的结尾
            cur.next = ListNode(val)
            cur = cur.next
            # 如果当前节点后续还有节点,也入堆
            if node.next:
                heapq.heappush(heaq, (node.next.val, idx, node.next))
        
        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
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

141. 环形链表

解题思路:快慢指针,快的一次走两步,慢的一步,如果会相等,说明有环。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # 快慢指针,如果相遇,就说明有环
        slow, fast = head,head
        # 循环遍历
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 如果指针相等,说明有环
            if slow == fast:
                return True
        return False
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

142. 环形链表 II

解题思路:
两阶段:第一阶段使用快慢指针,找到相遇点,第二阶段重置某个指针,两个指针速度一致,返回指针相遇时的节点。

步骤:
1.初始化快慢指针,找到相遇时的指针状态
2.重置慢指针到头节点,创建循环(当两个指针不相等),返回相遇时的指针所在的节点。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 处理特殊情况
        if not head or not head.next:
            return None
        # 先找到环,此时快慢指针相遇
        slow, fast = head,head
        # 找到环
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 遇到环,终止循环
            if slow == fast:
                break
        # 重置慢指针,将两个指针的速度调相同
        # 直到快慢指针相遇
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
            
        return 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

160. 相交链表

解题思路:

最直观的想法是,如果两个链表长度一样,那他们的相交节点就能通过逐个遍历节点找到了。
面对不同长度的链表,怎么才能使其在相交节点之前的长度一样呢?
那就是先遍历完链表1,再遍历链表2.在两个指针分别逆向(a指针遍历链表1-2,b指针遍历链表2-1)遍历,就同步了这两个链表的遍历。使得他们可以在相交点相遇。
时间复杂度O(N+M),其中 N 和 M 是两个链表的长度

步骤:

1.初始化链表a、b的指针
2.创建循环,直到a和b重合。a先遍历链表a,再遍历链表b;b同理
3.重合时的指针a或b即为所求。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        # 设置两个链表的指针
        cur_a,cur_b = headA, headB
        # 如果两个指针不重合
        while cur_a != cur_b:
            # cur_a先遍历链表a
            if cur_a:
                cur_a = cur_a.next
            # 遍历完成后转向遍历b
            else:
                cur_a = headB
            # cur_b同理
            if cur_b:
                cur_b = cur_b.next
            else:
                cur_b = headA
        # 返回重合时的指针
        return cur_a

  • 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

19. 删除链表的倒数第 N 个结点

解题思路:

最开始想两次反转链表,但是只有两个节点的情况下老是过不了(因为我考虑的是至少三个节点),遂放弃。

正确的方法是 快慢指针。先让快指针跑个n+1步,然后让快慢指针一起跑,直到快指针到了末尾,这个时候慢指针就是倒数第n+1个节点。再将其指向改为下下个节点即可。

步骤

1.初始化哑结点,快慢指针指向哑结点
2.快指针移动n+1个
3.快慢指针同时移动到快指针达到末尾
4.将慢指针的指向指向下下个节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 哑结点
        dummy = ListNode(0)
        dummy.next = head
        # 初始化快慢指针
        slow = fast = dummy
        # 快指针先移动n+1步
        for _ in range(n+1):
            fast = fast.next
        # 同时移动快慢指针,当快指针到到末尾,说明慢指针也到达了倒数第n+1个节点
        while fast:
            slow = slow.next
            fast = fast.next
        
        # 将倒数第n+1个节点指向倒数第n-1个节点,倒数第n个节点指向空
        # n_node = slow.next # 暂存第n个节点
        slow.next = slow.next.next
        # n_node.next = None # 将第n个节点指向空
        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
  • 23
  • 24
  • 25

143. 重排链表

解题思路:

可以转换为回文链表的思路。先从中点拆分,再交叉合并。

根据寻找中点的不同,可以分为两种步骤:

步骤1

1.找中点的快慢指针初始化为head,head.next,偶数时处于靠前的中点
2.将中点后的链表作为右子链表,切断左右子链表的链接
3.反转右子链表
4.交叉合并,设置一个哑结点。因为左子链表在奇数时会多一个中点,所以在同时合并两个子链表的前面位数的节点后,还需要加上左边剩余的节点。此时每次循环都分别消耗一个左右子链表的节点 (跟步骤二的不同,认为好理解点)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """

        slow,fast = head,head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 此时的slow在偶数个节点时实际是两个中点前一个节点,在奇数时是正确的中点
        mid = slow.next
        # 左右子链表分割
        slow.next = None
        # 反转右边
        pre = None
        cur = mid
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        
        # 左右子链表交叉合并
        left_node = head
        right_node = pre
        # 哑结点
        dummy = ListNode(0)
        dummy.next=head
        cur = dummy
        # 在偶数个时,左右子链表长度相等;在奇数个时,中点是在左子链表最后的;将其交叉合并,最后剩余一个中点,加到尾部
        while left_node and right_node:
            cur.next = left_node
            left_node = left_node.next
            cur = cur.next

            cur.next = right_node
            right_node = right_node.next
            cur = cur.next
        
        if left_node:
            cur.next = left_node
            
  • 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

步骤二

1.找中点的快慢指针初始化为head,head.next,偶数时处于靠前的中点
2.将中点后的链表作为右子链表,切断左右子链表的链接
3.反转右子链表
4.交叉合并。直接使用左子链表的头结点作为上一个步骤的哑结点,而后面也都是消耗了左右分别一个节点,所以规避掉了多余一个中点的问题。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # 特殊情况的处理
        if not head or not head.next:
            return head

        # 找中点
        slow,fast = head,head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 此时的slow在偶数个节点时实际是两个中点前一个节点,在奇数时是唯一的中点(正好停在中点)

        # 反转右子链表
        pre = None
        cur = slow.next # 指针指向 偶数时靠后的中点,奇数时指向中点后的节点
        slow.next = None # 断开左右子链表的链接,这下从头结点只能检测到中点了,确保不会访问到右子链表
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        
        # 左右子链表交叉合并
        left_node = head # 左子链表的头节点
        right_node = pre # 右子链表的头节点
        # 在偶数个时,左右子链表长度相等;在奇数个时,中点是在左子链表最后的;将其交叉合并,最后剩余一个中点,加到尾部
        # 由于采用while left_node and right_node:,所以不要担心右边节点少一个的情况
        while left_node and right_node:
            # 暂存左右子链表头节点的下一个节点
            temp_left, temp_right = left_node.next, right_node.next
            # 以下两行实现交叉合并,同时始终以左子链表的节点为开始
            # 将左子链表的头节点指向右子链表的头节点
            left_node.next = right_node
            # 右子链表的头节点 指向 左子链表头节点的下一个节点
            right_node.next = temp_left
            # 移动左右子链表节点到下一个节点
            left_node, right_node = temp_left, temp_right
            
  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/872048
推荐阅读
相关标签
  

闽ICP备14008679号