冲击大厂算法面试=＞链表专题【链表简单分割】

devtools/2024/9/22 19:15:25/

目录标题

分隔链表【一分为二】
- 上代码
- 题解呀
- 空间优化？
- 实在不会的时候记住

分隔 链表【一分为二】

在这里插入图片描述

感觉会又有点不会！！！😢
请添加图片描述

上代码

class Solution {/*** 一个链表的分区算法，该算法根据给定值 x 将链表分为两部分：一部分包含所有小于 x 的节点，另一部分包含所有大于等于 x 的节点。最终，这两部分链表被连接在一起返回*/public ListNode partition(ListNode head, int x) {//使用虚拟头结点：使边界条件更简单，避免在处理链表头节点时的额外检查//preHead：作为原始链表的头结点的前驱，便于操作原链表ListNode preHead = new ListNode(-1);preHead.next = head;//使用 cur 遍历原链表，从 head 开始直到链表末尾ListNode cur = preHead;//双链表构造：分别构造两个链表，最后再合并，避免了在原链表上直接修改带来的复杂性//leftPreNode 和 rightPreNode：分别用于构建小于 x 和大于等于 x 的新链表的头结点前驱ListNode leftPreNode = new ListNode(-10);ListNode leftNode = leftPreNode;ListNode rightPreNode = new ListNode(-10);ListNode rightNode = rightPreNode;while (cur.next != null) {//节点复制：为避免改变原链表，创建了新节点进行操作，虽然牺牲了一些空间效率，但简化了逻辑if (cur.next.val < x) {leftNode.next = new ListNode(cur.next.val);leftNode = leftNode.next;} else {rightNode.next = new ListNode(cur.next.val);rightNode = rightNode.next;}cur = cur.next;}//完成遍历后，将左侧链表的尾部指向右侧链表的头部（即 rightPreNode.next），形成完整的分区后的链表leftNode.next = rightPreNode.next;//将右侧链表的尾部指向 null，确保链表正确终止。rightNode.next = null;//head没变=1->4->3->2->5->2//返回左侧链表的头结点（即 leftPreNode.next），因为整个分区后的链表是以左侧链表开始return leftPreNode.next;}
}

题解呀

比较简单，就是把一个链表一分为二，然后再连接

请添加图片描述

在这里插入图片描述

空间优化？

直接将new ListNode(cur.next.val) 改成 cur.next 就行

while (cur.next != null) {if (cur.next.val < x) {leftNode.next = cur.next;leftNode = leftNode.next;} else {rightNode.next = cur.next;rightNode = rightNode.next;}cur = cur.next;
}