GVKun编程网logo

leetcode 148. Sort List 排序链表(中等)（list排序sort原理）

19

最近很多小伙伴都在问leetcode148.SortList排序链表(中等)和list排序sort原理这两个问题，那么本篇文章就来给大家详细解答一下，同时本文还将给你拓展(Java)LeetCode8

最近很多小伙伴都在问leetcode 148. Sort List 排序链表(中等)和list排序sort原理这两个问题，那么本篇文章就来给大家详细解答一下，同时本文还将给你拓展(Java) LeetCode 82. Remove Duplicates from Sorted List II —— 删除排序链表中的重复元素 II、(Java) LeetCode 83. Remove Duplicates from Sorted List —— 删除排序链表中的重复元素、148. Sort List - LeetCode、148. 排序链表Sort List等相关知识，下面开始了哦！

本文目录一览：

leetcode 148. Sort List 排序链表(中等)（list排序sort原理）

leetcode 148. Sort List 排序链表(中等)（list排序sort原理）

一、题目大意

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

**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

二、解题思路

用快慢指针将列表分成两部分，将两部分列表递归排序，再将排序后的列表合并

三、解题方法

3.1 Java实现

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 使用快慢指针找出中间节点，将链表一分为二
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        return merge(sortList(head), sortList(mid));
    }

    ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                tail.next = l2;
                l2 = l2.next;
            } else {
                tail.next = l1;
                l1 = l1.next;
            }
            tail = tail.next;
        }
        if (l1 != null) {
            tail.next = l1;
        }
        if (l2 != null) {
            tail.next = l2;
        }
        return dummy.next;
    }
}

四、总结小记

  • 2022/9/3 要与邻里打好交道，远亲不如近邻呀

(Java) LeetCode 82. Remove Duplicates from Sorted List II —— 删除排序链表中的重复元素 II

(Java) LeetCode 82. Remove Duplicates from Sorted List II —— 删除排序链表中的重复元素 II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5　　

Example 2:

Input: 1->1->1->2->3
Output: 2->3

 

这道题是LeetCode 83. Remove Duplicates from Sorted List —— 删除排序链表中的重复元素升级版。区别就是这道题不能保留重复的节点。这就引发了一个问题，如果第一个节点就是重复的要怎么办。迭代方法的话很自然的想到要建立一个假节点连到头结点前进行处理，并且要时刻保持指针指在重复节点的前驱节点上。

第一步，建立假节点链接在表头前，并建立指针指向假节点，即从假节点开始遍历链表；

第二步，判断当前指针的next以及next的next是否相同，即找到没有重复值得节点，此时注意前驱节点要一直保留，即只移动next指向的节点，见代码；

第三步，将当前指针的next指向第一个没有重复过的节点，后移指针，并重复上述过程。

 

递归方法还是更容易直观简洁一些：

先看头节点是不是重复的，如果是重复的，那就从头结点后第一个非重复节点（这里的非重复节点是指和头结点值不同的节点，而不是在整个链表不存在重复值的节点）开始重新调用函数；

如果头结点不是重复的，那么递归调用头结点之后的节点。

递归方法简洁吊打迭代方法，见代码。

 

迭代解法（Java）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head; //建立假节点指向表头
        head = dummy; //建立指针从假节点遍历，这里用head作为指针节省一点儿空间
        while (head.next != null && head.next.next != null) { //特殊情况处理，即空链表和单节点的链表
            if (head.next.val == head.next.next.val) { //找到后继中第一个不重复的节点
                int val = head.next.val; //记录一下后继的值，便于后面搜索
                while(head.next != null && head.next.val == val) 
                    head.next = head.next.next; //只改变后继的next域，这样做可以保证前驱一直指向重复节点的头，因此找到节点后使驱现在指向第一个不重复的节点，相当于跨过所有重复的节点
            }
            else 
                head = head.next; //将指针移动到找到的第一个不重复的节点
        }
        return dummy.next; //返回
    }
}

 

递归解法（Java）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head; //处理特殊情况，即空链表和单节点链表
        ListNode cur = head.next; //建立一个指针，扫描头结点后面的节点，意为看头结点是否是重复节点
        if (cur.val != head.val) { //如果头结点不是重复节点
            head.next = deleteDuplicates(cur); //头结点的next就指向递归调用后的cur节点，cur几点就是头结点的后继
            return head; //返回全部递归调用后的头结点
        }
        else { //如果头结点是重复节点
            while (cur != null && cur.val == head.val) cur = cur.next; //找到第一个和头结点值不同的节点，并返回递归调用这个节点的结果
            return deleteDuplicates(cur);
        }
    }
}

 

(Java) LeetCode 83. Remove Duplicates from Sorted List —— 删除排序链表中的重复元素

(Java) LeetCode 83. Remove Duplicates from Sorted List —— 删除排序链表中的重复元素

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

 

很简单的链表问题，可以写成递归和迭代两种形式。具体思路：

第一步，寻找第一个节点值和当前表头所指的节点值不同的节点；

第二步，让当前表头节点的next指向找到的节点；

第三部，递归调用前两步，或迭代调用前两步。

 

详细代码注解见下。

 

递归解法（Java）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head; //特殊情况处理，即空链表和单节点链表直接返回
        ListNode cur = head.next; //设定指针指向表头后的第一个节点
        while (cur != null && cur.val == head.val) cur = cur.next; //第一步，寻找第一个节点值和当前表头节点所指节点值不同的节点
        head.next = deleteDuplicates(cur); //找到后，进行第二步，即让当前表头节点的next指向刚才找到的节点。这里用了递归调用，上面找到的不重复节点是cur，那么这个递归返回的恰恰是cur，且同时执行以cur为节点头的去重工作
        return head; //返回头结点
    }
}

 

迭代解法（Java）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head; //特殊情况处理，同迭代解法
        ListNode pre = head, cur = head.next; //定义两个指针分别指向当前头节点和其下一个节点
        while (cur != null) {
            if (cur.val == pre.val) cur = cur.next; //第一步，寻找第一个非重复节点
            else { 
                pre.next = cur; //找到后进行第二步，即让当前节点pre的next指向找到的节点cur
                pre = cur; //之后重复之前的过程
                cur = pre.next; 
            }
        }
        pre.next = cur; //迭代到最后因为cur为null的时候就跳出循环了，没有执行最后的去重，所以加一句让链表末尾没有重复节点
        return head;
    }
}

 

148. Sort List - LeetCode

148. Sort List - LeetCode

Solution

148. Sort List

Question

题目大意:对链表进行排序

思路:链表转为数组,数组用二分法排序

Java实现:

public ListNode sortList(ListNode head) {
    // list to array
    List<Integer> list = new ArrayList<>();
    ListNode cur = head;
    while (cur != null) {
        list.add(cur.val);
        cur = cur.next;
    }
    // quicksort
    // quicksort(list);
    Collections.sort(list);
    // Arrays.sort(arr);
    // array to list
    cur = head;
    for (int tmp : list) {
        cur.val = tmp;
        cur = cur.next;
    }
    return head;
}

148. 排序链表Sort List

148. 排序链表Sort List

148. 排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:
输入: 4->2->1->3
输出: 1->2->3->4

示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

分析：和这道题差不多阿，都是链表，用归并排序做。题目要求O(nlogn)，好像就是快排和归并? 递归的关键是写出递推公式和的终止条件。
分治思想，每次都用q分隔(p..r)

递推公式：
merge_sort(p..r) = merge(merge_sort(p..q), merge_sort(q+1..r))
终止条件：
p >= r 不用再继续分解

图片描述

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }
}

参考： 极客时间 王争 算法与数据结构之美

关于leetcode 148. Sort List 排序链表(中等)和list排序sort原理的介绍现已完结，谢谢您的耐心阅读，如果想了解更多关于(Java) LeetCode 82. Remove Duplicates from Sorted List II —— 删除排序链表中的重复元素 II、(Java) LeetCode 83. Remove Duplicates from Sorted List —— 删除排序链表中的重复元素、148. Sort List - LeetCode、148. 排序链表Sort List的相关知识，请在本站寻找。

本文标签：

上一篇docker 在已有的 tomcat 镜像上打新的镜像的 Dockerfile 编写说明（docker 使用镜像）

下一篇leetcode 101. Symmetric Tree 对称二叉树(简单)（对称的二叉树）

相关文章