LeetCode148. 排序链表🌟🌟中等

算法系统课免费

课后作业

问题描述

给你链表的头结点 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
}

class Solution { public ListNode sortList(ListNode head) { if(head == null || head.next == null){ return head; } //1.用中间节点(middleNode函数)把链表拆成两个链表，2.两个链表执行递归调用， //3.合并两个有序链表，合并函数(mergeTwoLists)，4返回新链表 //1.中间节点mid =2 //ListNode mid = middleNode(head); ListNode mid = middleNode(head); // 拆链表。一定要注意前链表的最后一个节点的next = null，！！！！ ListNode left = head; //left=4 ListNode right = mid.next; //right=1 mid.next = null; // 不要漏掉 //2.left,right两个链表执行递归调用 ListNode newleft = sortList(left); ListNode newright = sortList(right); //3.合并两个有序链表 ListNode mergeLists = mergeTwoLists(newleft, newright); return mergeLists; } // 返回链表中间节点，如果节点个数是偶数，则返回第一个中间节点 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){ // 当两个链表都不为空 // 逐个判断他们的头节点，谁的小就放到临时节点上temp ListNode list3 = new ListNode(-1); // 虚拟头节点 ListNode temp = list3; while(list1 != null && list2 != null){ if(list1.val <= list2.val){ temp.next = list1; list1 = list1.next; temp = temp.next; }else{ temp.next = list2; list2 = list2.next; temp = temp.next; } } // 此时会有以某个最大值的链表还剩最后一个节点没放到 temp上 temp.next = list1 == null ? list2 : list1; // temp = 最后一个节点 return list3.next; // list3 = -1 ，list3.next为头节点 } }

while(fast!=nullptr&&fast->next!=nullptr){ fast=fast->next->next; slow=slow->next; } ListNode*mid=slow->next; slow->next=nullptr;//断链 return mid; } //合并链表并排序，返回头结点 ListNode* merge(ListNode*head1,ListNode*head2){ ListNode*dummyHead=new ListNode(0); ListNode*cur=dummyHead; while(head1!=nullptr&&head2!=nullptr){ if(head1->val<head2->val){ cur->next=head1; head1=head1->next; } else{ cur->next=head2; head2=head2->next; } cur=cur->next; } cur->next=(head1==nullptr)?head2:head1; return dummyHead->next; } ListNode* sortList(ListNode* head) { //剪枝0节点、1节点情况 if(head==nullptr||head->next==nullptr){ return head; } ListNode*head1=head; ListNode*head2=midNode(head); //对两边排序 head1=sortList(head1); head2=sortList(head2); //合并链表，返回头结点 return merge(head1,head2); }

/** * 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; } * } */ // 【思路】二路归并 + 有序列表排序 // 时间复杂度：O(n log n) // 空间复杂度：O(n) class Solution { public ListNode sortList(ListNode head) { //函数目的 //结束条件 if(head == null || head.next == null) { return head; } //关系式 ListNode left = head; ListNode temp = findMiddle(head); ListNode right = temp.next; temp.next = null; ListNode lHead = sortList(left); ListNode rHead = sortList(right); return mergeOrdered(lHead, rHead); } ListNode findMiddle(ListNode head) { //若是偶数则返回前一个 if(head == null) return head; ListNode slow = head; ListNode fast = head.next; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } ListNode mergeOrdered(ListNode head1, ListNode head2) { //合并两个有序链表 ListNode ans = new ListNode(-1); ListNode temp = ans; while(head1 != null && head2 != null) { if(head1.val < head2.val) { temp.next = head1; head1 = head1.next; } else { temp.next = head2; head2 = head2.next; } temp = temp.next; } temp.next = head1 == null ? head2 : head1; return ans.next; } } // 时间复杂度：O(n^2) > O(n log n) // 空间复杂度：O(n) // class Solution { // public ListNode sortList(ListNode head) { // ListNode newhead = new ListNode(-1); // ListNode ans = newhead; // while(head.next != null) { // ListNode head0 = head; // ListNode smaller = head; // ListNode pre = head; // while(head0.next != null) { // if(smaller.val > head0.next.val) { // smaller = head0.next; // pre = head0; // } // head0 = head0.next; // } // if(smaller != pre) { // pre.next = smaller.next; // smaller.next = null; // newhead.next = smaller; // } // else { // head = head.next; // newhead.next = smaller; // } // newhead = newhead.next; // } // newhead.next = head; // return ans.next; // } // }

class Solution { public ListNode sortList(ListNode head) { if(head == null || head.next == null) { return head; } // 找到中间节点 ListNode mid = findMid(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; } // 寻找中间节点 ListNode findMid(ListNode head) { if(head == null || head.next == null) return head; ListNode fast = head; ListNode slow = head; while(fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } // 合并两个链表 ListNode mergeTwoLists(ListNode a, ListNode b) { ListNode res = new ListNode(0); ListNode cur = res; while (a != null && b != null){ if(a.val <= b.val) { cur.next = a; a = a.next; } else { cur.next = b; b = b.next; } cur = cur.next; } cur.next = a == null ? b : a; return res.next; } }

class Solution { // 这题比较经典，拆解开可以包含之前的多个题目 public ListNode sortList(ListNode head) { // 1.递归结束条件 if (head == null || head.next == null) { return head; } // 2.找到链表的中间节点截开，递归下探 ListNode midNode = findMidNode(head); ListNode midRightNode = midNode.next; midNode.next = null; // 断开操作 // 3.开始对两截链表递归排序 ListNode left = sortList(head); ListNode right = sortList(midRightNode); // 4.合并 return mergeTwoListNode(left, right); } /** 找到链表中间节点（876. 链表的中间结点） */ private ListNode findMidNode(ListNode head) { // 双指针快慢指针 if (head == null || head.next == null) { return head; } ListNode slow = head; ListNode fast = head; // slow指向链表的上中点 while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } /** 合并两个有序链表（21. 合并两个有序链表） */ private ListNode mergeTwoListNode(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode tmp = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { tmp.next = l1; l1 = l1.next; } else { tmp.next = l2; l2 = l2.next; } tmp = tmp.next; } tmp.next = l1 != null ? l1 : l2; return dummy.next; } }

发表回复取消回复

后才能评论

少年不识流川枫永久会员 2024年2月28日下午7:14

注意拆表，前链表的最后一个节点的next = null，！！！！
前链表的最后一个节点的next = null，！！！！
前链表的最后一个节点的next = null，！！！！
搞忘了

Yuki 永久会员 2024年2月2日上午10:15

重写
https://leetcode.cn/problems/sort-list/solutions/2628568/148-pai-xu-lian-biao-by-yukislab-1s6x

登录以回复

Yuki 永久会员 2024年1月31日上午11:22

打卡

class Solution {
public:
//快慢指针找中间节点，中间节点归到链表1，返回中间节点的下一个
ListNode* midNode(ListNode* head){
ListNodeslow=head;
ListNodefast=head->next;

};
/*
思路：归并排序=划分+合并（三个函数：找中间节点、排序、整体逻辑）
1）整体逻辑多次重复->使用递归
2）找中间节点：双指针
*/

uu 永久会员 2023年9月21日下午4:47

AD钙奶普通 2023年9月1日下午4:15

阿尚普通 2023年8月18日下午3:01

帅气的冬瓜普通 2023年6月29日上午9:51

打卡

登录以回复

课后作业

问题描述

代码实现

Java

Python

C++

Go

发表回复 取消回复

评论(7)

付款后无法显示下载地址或者无法查看内容？

发表回复取消回复