Java数据结构中链表分割及链表排序使用快速排序、归并排序、集合排序、迭代、递归，刷题的重点总结

拼搏现实的明天。 2024-03-26 11:32 10阅读 0赞

### 本篇主要介绍在单链表进行分割，单链表进行分隔并使用快速排序、归并排序、集合排序、迭代、递归等方法的总结，愿各位大佬喜欢~~ ###

[86. 分隔链表 - 力扣（LeetCode）][86. _ - _LeetCode]

[148. 排序链表 - 力扣（LeetCode）][148. _ - _LeetCode]

--------------------

**目录**

一、分隔链表

二、排序链表

2.1先介绍一个最容易最简单的方法

2.2普通归并排序（自顶向下）

2.3借鉴大佬的归并排序（自底向上也是最难的，空间复杂度o(1)）

2.4面试官让你用快排实现，不会做也得会

2.5快排2：

--------------------

## 一、分隔链表 ##

> [86. 分隔链表 - 力扣（LeetCode）][86. _ - _LeetCode]
> 
> 给你一个链表的头节点 `head` 和一个特定值`x` ，请你对链表进行分隔，使得所有 **小于** `x` 的节点都出现在 **大于或等于** `x` 的节点之前。
> 
> 在分隔链表时，先考虑如何去分隔链表，怎么保证节点的next不形成环。

![f63efd85898d47849644cc44f4d0dfce.png][]

> 方法一：也是笨方法，找到第一个>x的值将小的值都逐个进行头插，随后将next指向第一个>x的值

class Solution {
        public ListNode partition(ListNode head, int x) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode mark = new ListNode(0, head);
            ListNode cur1 = mark;
            while (cur1.next != null && cur1.next.val < x) {
                cur1 = cur1.next;
            }
            ListNode firstMaxOrNull = cur1.next;
            ListNode cur2 = cur1;
            while (cur2 != null && cur2.next != null) {
                if (cur2.next.val >= x) {
                    cur2 = cur2.next; 
                } else {
                    cur1.next = cur2.next;
                    cur2.next = cur2.next.next;
                    cur1 = cur1.next;
                    cur1.next = null;
                }
            }
            cur1.next = firstMaxOrNull;
            return mark.next;
        }
    }

> 方法二：创建俩个链表进行分别插入，最后合并俩个链表

public ListNode partition(ListNode head, int x) {
            ListNode minLink = new ListNode(0);//记录小值链表的头
            ListNode minP = minLink;//对小表操作用的指针
    
            ListNode maxLink = new ListNode(0);//记录大值链表的头
            ListNode maxP = maxLink;//同理
    
            while(head!=null){
                if(head.val < x){//找到小的值
                    minP.next = head;//放入minLink中，操作指针后移一位
                    minP = head;
                }else{
                    maxP.next = head;//放入maxLink中，操作指针后移一位
                    maxP = head;
                }
                head = head.next;
            }
            //遍历完成后记得后一段链表的最后节点指向null;
            maxP.next = null;
            //两段拼接
            minP.next = maxLink.next;
    
            return minLink.next;
        }

## **二、排序链表** ##

> [148. 排序链表 - 力扣（LeetCode）][148. _ - _LeetCode]
> 
> 给你链表的头结点 `head` ，请将其按 **升序** 排列并返回 **排序后的链表** 。
> 
> 上一道题并没有让合并之后还要进行排序，本题不仅要分隔之后还要进行排序，此时可以想到很多种方法，比如堆排序，快速排序，归并排序等等。看似简单，却是很多大厂的面试题。
> 
> 题目的进阶问题要求达到 O(nlogn) 的时间复杂度和 O(1) 的空间复杂度
> 
> 时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O（n^2），其中最适合链表的排序算法是归并排序。

![2751f164c5ab48c491f54bffe2d5f257.png][]

#### 2.1先介绍一个最容易最简单的方法 ####

> 都存到集合中，排序后再进行赋值，如果写出这样，面试可能要回家喽！！！

class Solution {
        //思路，先把链表存到数组，排序后重新更新链表
        public ListNode sortList(ListNode head) {
            ArrayList<Integer> list = new ArrayList();
            ListNode p = head;
            while(p != null){
                list.add(p.val);
                p = p.next;
            }
            Collections.sort(list);
            p = head;
            for(int i = 0;i<list.size();i++){
                p.val = list.get(i);
                p = p.next;
            }
            return head;
        }
    }

#### 2.2普通归并排序（自顶向下） ####

> 使用快慢指针进行找到中间节点，然后进行归并排序

public ListNode sortList(ListNode head){
       return mergeSort(head);
    }
    
    // 找到一个链表的中点
        public ListNode findMid(ListNode head) {
            if (head == null) return head;
    
            ListNode fast = head.next;  // 快指针 每次走2步
            ListNode slow = head;       // 慢指针 每次走1步
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
    
    public ListNode mergeSort(ListNode head) {
            // 当head.next==null时 说明当前链表只有一个元素 无序再排序
            if (head == null || head.next == null) {
                return head;
            }
            // 找到中间节点
            ListNode mid = findMid(head);
            // 存储中间节点的下一个结点
            ListNode next = mid.next;
            // 从中间结点断开 分别对两边进行mergeSort
            mid.next = null;
            // 返回排序后的头节点
            ListNode left = mergeSort(head);
            ListNode right = mergeSort(next);
    
            // 返回合并之后的头节点
            return merge(left, right);
        }
    
        public ListNode merge(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(-1);
            ListNode curr = dummy;
            while (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    curr.next = l1;
                    l1 = l1.next;
                } else {
                    curr.next = l2;
                    l2 = l2.next;
                }
                curr = curr.next;
            }
    
            if (l1 != null) {
                curr.next = l1;
            }
    
            if (l2 != null) {
                curr.next = l2;
            }
            return dummy.next;
        }

#### 2.3借鉴大佬的归并排序（自底向上也是最难的，空间复杂度o(1)） ####

class Solution {
        public ListNode sortList(ListNode head) {
            ListNode dummy = new ListNode(-1, head);
            // 获取链表的长度
            int len = 0;
            ListNode curr = head;
            while (curr!=null) {
                len++;
                curr = curr.next;
            }
    
            // 循环遍历
            // 外层遍历step 内层处理每step个元素进行一次merge
            for (int step=1; step<len; step*=2) {
                ListNode tail = dummy;
                curr = dummy.next;
                while (curr!=null) {
                    ListNode left = curr;
                    ListNode right = cut(left, step);
                    curr = cut(right, step);
                    tail.next = merge(left, right);
                    while (tail.next!=null) {
                        tail = tail.next;
                    }
                }
            }
        return dummy.next;
        }
    
        // 将链表从from开始切掉前step个元素，返回后一个元素
        public ListNode cut(ListNode from, int step) {
            step--;
            while (from!=null && step>0) {
                from = from.next;
                step--;
            }
            if (from==null) {
                return null;
            } else {
                ListNode next = from.next;
                from.next = null;
                return next;
            }
        }
    
        // 将两个有序链表合并成一个，返回合并后的头节点
        public ListNode merge(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode();
            ListNode curr = dummy;
            while (l1!=null && l2!=null) {
                if (l1.val<l2.val) {
                    curr.next = l1;
                    l1 = l1.next;
                } else {
                    curr.next = l2;
                    l2 = l2.next;
                }
                curr = curr.next;
            }
            if (l1!=null) {
                curr.next = l1;
            }
            if (l2!=null) {
                curr.next = l2;
            }
            return dummy.next;
        }
    }

#### 2.4面试官让你用快排实现，不会做也得会 ####

public ListNode sortList3(ListNode head) {
            return quickSortLinkedList(head)[0];
        }
    
        public ListNode[] quickSortLinkedList(ListNode head) {
            if(head == null || head.next == null) return new ListNode[]{head,head};
            //pivot为head，定义跟踪分割左右两个链表的头尾指针
            ListNode p = head.next,headSmall= new ListNode(),
                    headBig = new ListNode(),tailSmall = headSmall, tailBig = headBig;
    
            //partition操作，以pivot为枢纽分割为两个链表
            while(p != null){
                if(p.val < head.val){
                    tailSmall.next = p;
                    tailSmall = tailSmall.next;
                }else{
                    tailBig.next = p;
                    tailBig = tailBig.next;
                }
                p = p.next;
            }
    
            //断开<pivot的排序链表、pivot、>=pivot的排序链表，链表变为三个部分
            head.next = null;
            tailSmall.next = null;
            tailBig.next = null;
    
            //递归partition
            ListNode[] left = quickSortLinkedList(headSmall.next);
            ListNode[] right = quickSortLinkedList(headBig.next);
    
    
            //如果有<pivot的排序链表、连接pivot
            if(left[1] != null) {
                left[1].next = head;
            }
            //连接pivot、>=pivot的排序链表
            head.next = right[0];
    
            //确定排序后的头节点和尾节点
            ListNode newHead,newTail;
            if(left[0] != null) newHead = left[0];
            else newHead = head;
            if(right[1] != null) newTail = right[1];
            else newTail = head;
    
            //返回当前层递归排序好的链表头节点和尾节点
            return new ListNode[]{newHead,newTail};
        }

#### 2.5快排2： ####

> 用6个指针，分别指向小于部分的头`h1`和尾`t1`、等于部分的头`h2`和尾`t2`、大于部分的头`h3`和尾`t3`。

class Solution {
        public ListNode sortList(ListNode head) {
            return quickSort(head);
        }
    
        public ListNode quickSort(ListNode head) {
            if (head==null || head.next==null) {
                return head;
            }
            ListNode h1 = new ListNode();
            ListNode h2 = new ListNode();
            ListNode h3 = new ListNode();
            ListNode t1 = h1;
            ListNode t2 = h2;
            ListNode t3 = h3;
            ListNode curr = head;
            int pivot = getMid(head).val;  // 用中间节点的原因是，如果每次用最左边的结点，对于纯递增和纯递减的case就退化为O(n)
    
            while (curr!=null) {
                ListNode next = curr.next;
                if (curr.val < pivot) {
                    curr.next = null;
                    t1.next = curr;
                    t1 = t1.next;
                } else if (curr.val == pivot) {
                    curr.next = null;
                    t2.next = curr;
                    t2 = t2.next;
                } else {
                    curr.next = null;
                    t3.next = curr;
                    t3 = t3.next;
                }
                curr = next;
            }
    
            // < 的链表和 > 的链表分别快排
            h1 = quickSort(h1.next);
            h3 = quickSort(h3.next);
    
            // h1链表不一定有元素 h2链表一定有元素 先把h2、h3连起来
            h2 = h2.next;
            t2.next = h3;
            // 如果h1链表为空 直接返回h2即可
            // 否则找到h1链表的结尾，连上h2的头
            if (h1==null) {
                return h2;
            } else {
                t1 = h1;
                // 找到t1链表的结尾
                while (t1.next!=null) {
                    t1 = t1.next;
                }
                t1.next = h2;
                return h1;
            }
        }
    
        public ListNode getMid(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while (fast!=null && fast.next!=null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
    
    }

##  ##

> merge 函数里只有一个 dummy 指针是新建的，后续节点都是直接拼接原链表的数据，所以一次 merge 操作的空间复杂度是 O(1)。而且 CPU 一次只能执行一个 merge 函数，merge 函数执行一次后，栈上申请的空间都释放掉了，所以，没有递归的解法，总的空间复杂度还是 O(1)。

[86. _ - _LeetCode]: https://leetcode.cn/problems/partition-list/
[148. _ - _LeetCode]: https://leetcode.cn/problems/sort-list/
[f63efd85898d47849644cc44f4d0dfce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/26205ce6a1c44bca90329469186e98d1.png
[2751f164c5ab48c491f54bffe2d5f257.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/938d987277b849e982b22eb416d0cd58.png