LeetCode148. 排序链表🌟🌟中等

课后作业

问题描述

原文链接：148. 排序链表

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

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 104] 内
• -105 <= Node.val <= 105

代码实现

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        // 递归结束条件
        if(head == null || head.next == null){
            return head;
        }
        // 先找到中间节点
        ListNode mid = middleNode(head);
        // 拆分左右两个链条
        ListNode left = head;
        ListNode right = mid.next;
        mid.next = null;
        // 两边递归排序
        ListNode lHead = sortList(left);
        ListNode rHead = sortList(right);
        // 合并有序链表
        ListNode mergeHead = mergeTwoLists(lHead, rHead);

        return mergeHead;

    }



    // 返回链表中间节点，如果节点个数是偶数，则返回第一个中间节点
    public ListNode middleNode(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;

        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;

    }
    // 合并两个有序的链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode list3 = new ListNode(-1);
        ListNode temp = list3;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
               temp.next = list1;
               list1 = list1.next;

            } else {
               temp.next = list2;
               list2 = list2.next;
            }
            temp = temp.next;
        }
        temp.next = list1 == null ? list2 : list1;
        return list3.next;
    }
}

Python

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

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 递归结束条件
        if head == None or head.next == None:
            return head

        # 先找到中间节点
        mid = self.middleNode(head)

        # 拆分左右两个链条
        left = head
        right = mid.next
        mid.next = None

        # 两边递归排序
        lHead = self.sortList(left)
        rHead = self.sortList(right)

        # 合并有序链表
        mergeHead = self.mergeTwoLists(lHead, rHead)

        return mergeHead


    # 返回链表中间节点，如果节点个数是偶数，则返回第一个中间节点
    def middleNode(self, head):
        if head == None or head.next == None:
            return head
        slow = head
        fast = head
        while fast.next != None and fast.next.next != None:
            fast = fast.next.next
            slow = slow.next
        return slow

    # 合并两个有序的链表
    def mergeTwoLists(self, list1, list2):
        list3 = ListNode(-1)
        temp = list3
        while list1 != None and list2 != None:
            if list1.val <= list2.val:
                temp.next = list1
                list1 = list1.next
            else:
                temp.next = list2
                list2 = list2.next
            temp = temp.next
        temp.next = list1 if list1 != None else list2
        return list3.next

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 递归结束条件
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        // 先找到中间节点
        ListNode* mid = middleNode(head);

        // 拆分左右两个链条
        ListNode* left = head;
        ListNode* right = mid->next;
        mid->next = nullptr;

        // 两边递归排序
        ListNode* lHead = sortList(left);
        ListNode* rHead = sortList(right);

        // 合并有序链表
        ListNode* mergeHead = mergeTwoLists(lHead, rHead);

        return mergeHead;
    }

    // 返回链表中间节点，如果节点个数是偶数，则返回第一个中间节点
    ListNode* middleNode(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* slow = head;
        ListNode* fast = head;

        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }

        return slow;
    }

    // 合并两个有序的链表
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* list3 = new ListNode(-1);
        ListNode* temp = list3;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                temp->next = list1;
                list1 = list1->next;

            } else {
                temp->next = list2;
                list2 = list2->next;
            }
            temp = temp->next;
        }

        temp->next = list1 == nullptr ? list2 : list1;
        return list3->next;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    // 递归结束条件
    if head == nil || head.Next == nil {
        return head
    }

    // 先找到中间节点
    mid := middleNode(head)

    // 拆分左右两个链条
    left := head
    right := mid.Next
    mid.Next = nil

    // 两边递归排序
    lHead := sortList(left)
    rHead := sortList(right)

    // 合并有序链表
    mergeHead := mergeTwoLists(lHead, rHead)

    return mergeHead
}

// 返回链表中间节点，如果节点个数是偶数，则返回第一个中间节点
func middleNode(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    slow := head
    fast := head

    for fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }

    return slow
}

// 合并两个有序的链表
func mergeTwoLists(list1, list2 *ListNode) *ListNode {
    list3 := &ListNode{-1, nil}
    temp := list3

    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            temp.Next = list1
            list1 = list1.Next
        } else {
            temp.Next = list2
            list2 = list2.Next
        }
        temp = temp.Next
    }

    if list1 == nil {
        temp.Next = list2
    } else {
        temp.Next = list1
    }

    return list3.Next
}

帅地训练营会员

打赏 收藏 海报挣佣金 推广链接