【LeetCode】148. 排序链表

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 reorderList(self, head: ListNode) -> None:
        """ Do not return anything, modify head in-place instead. """
        mid = self.splitList(head)
        # 将 mid 开头的这部分链表翻转
        head2 = self.reverseList(mid)
        return self.mergeList(head,head2)
        

    # 二分链表
    def splitList(self,head):
        slow = fast = head
        while(fast.next and fast.next.next):
            fast = fast.next.next
            slow = slow.next
        tmp = slow.next
        slow.next = None
        return tmp
    
    # 翻转链表
    def reverseList(self,head):
        pre = None
        start = head
        while(start):
            tmp = start.next 
            start.next = pre
            pre = start
            start = tmp        
        return pre

    # 交叉合并
    def mergeList(self,head1,head2):
        cnt = 0         
        tail = head = head1 # 最后返回的头节点
        head1 = head1.next 
        while(head1 and head2):
            if cnt % 2 == 0:
               tail.next = head2
               head2 = head2.next
            else:
                tail.next = head1
                head1 = head1.next
            tail = tail.next
            cnt += 1
        if head1:
            tail.next = head1
        if head2:
            tail.next = head2
        return head