148.md

题目

给你链表的头节点head, 请将其按升序排列并返回排序后的链表

解题思路

1. 通过快慢指针,找到链表中点
2. 断链操作,切掉链表的前n个节点,并返回后半部分的链表头
3. 合并两个有序链表

Python语言版本

# 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 getLength(head):
            res = 0
            while head:
                head = head.next
                res += 1
            return res
        
        def split(head, step):
            # 断链操作,返回第二部分的链表头
            if not head:
                return None
            curr = head
            for _ in range(1, step):
                if not curr.next:
                    break
                curr = curr.next
            res, curr.next = curr.next, None
            return res
        
        def merge(h1, h2):
            res = h = ListNode()
            while h1 and h2:
                if h1.val < h2.val:
                    h.next, h1 = h1, h1.next
                else:
                    h.next, h2 = h2, h2.next
                h = h.next
            h.next = h1 if h1 else h2
            return res.next
        
        length = getLength(head)
        dummy = ListNode()
        dummy.next = head
        step = 1

        while step < length:
            prev, curr = dummy, dummy.next
            while curr:
                h1 = curr
                h2 = split(h1, step)
                curr = split(h2, step)
                temp = merge(h1, h2)
                prev.next = temp
                while prev.next:
                    prev = prev.next
            step *= 2
        return dummy.next
        

C语言写法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {
    struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    struct ListNode *temp = dummyHead, *temp1 = head1, *temp2 = head2;
    while (temp1 != NULL && temp2 != NULL) {
        if (temp1->val <= temp2->val) {
            temp->next = temp1;
            temp1 = temp1->next;
        } else {
            temp->next = temp2;
            temp2 = temp2->next;
        }
        temp = temp->next;
    }
    if (temp1 != NULL) {
        temp->next = temp1;
    } else if (temp2 != NULL) {
        temp->next = temp2;
    }
    return dummyHead->next;
}

struct ListNode* sortList(struct ListNode* head) {
    if (head == NULL) {
        return head;
    }
    int length = 0;
    struct ListNode* node = head;
    while (node != NULL) {
        length++;
        node = node->next;
    }
    struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    for (int subLength = 1; subLength < length; subLength <<= 1) {
        struct ListNode *prev = dummyHead, *curr = dummyHead->next;
        while (curr != NULL) {
            struct ListNode* head1 = curr;
            for (int i = 1; i < subLength && curr->next != NULL; i++) {
                curr = curr->next;
            }
            struct ListNode* head2 = curr->next;
            curr->next = NULL;
            curr = head2;
            for (int i = 1; i < subLength && curr != NULL && curr->next != NULL;
                 i++) {
                curr = curr->next;
            }
            struct ListNode* next = NULL;
            if (curr != NULL) {
                next = curr->next;
                curr->next = NULL;
            }
            struct ListNode* merged = merge(head1, head2);
            prev->next = merged;
            while (prev->next != NULL) {
                prev = prev->next;
            }
            curr = next;
        }
    }
    return dummyHead->next;
}

Go语言写法

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func merge(head1, head2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    temp, temp1, temp2 := dummyHead, head1, head2
    for temp1 != nil && temp2 != nil {
        if temp1.Val <= temp2.Val {
            temp.Next = temp1
            temp1 = temp1.Next
        } else {
            temp.Next = temp2
            temp2 = temp2.Next
        }
        temp = temp.Next
    }
    if temp1 != nil {
        temp.Next = temp1
    } else if temp2 != nil {
        temp.Next = temp2
    }
    return dummyHead.Next
}

func sortList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    length := 0
    for node := head; node != nil; node = node.Next {
        length++
    }

    dummyHead := &ListNode{Next: head}
    for subLength := 1; subLength < length; subLength <<= 1 {
        prev, cur := dummyHead, dummyHead.Next
        for cur != nil {
            head1 := cur
            for i := 1; i < subLength && cur.Next != nil; i++ {
                cur = cur.Next
            }

            head2 := cur.Next
            cur.Next = nil
            cur = head2
            for i := 1; i < subLength && cur != nil && cur.Next != nil; i++ {
                cur = cur.Next
            }

            var next *ListNode
            if cur != nil {
                next = cur.Next
                cur.Next = nil
            }

            prev.Next = merge(head1, head2)

            for prev.Next != nil {
                prev = prev.Next
            }
            cur = next
        }
    }
    return dummyHead.Next
}