力扣86——分隔链表
2010 年 8 月 10 日
原题
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5
原题url:https://leetcode-cn.com/problems/partition-list/
解题
题目很好理解,重点在于区分大于等于和小于目标值的节点,判断其实是很简单的,主要在于如何拼接链表,以及最终如何返回。
我发现,针对链表拼接的这种题目,常常可以通过添加辅助节点(辅助头结点或者辅助尾结点)来简化拼接操作。
这道题的话,需要针对两个区间都添加辅助头结点和尾结点,然后利用一个 current 节点进行遍历,扫描到大于等于目标值的节点,添加到相应区间的尾结点,再将尾结点后移;小于目标值的节点,添加到相应区间的尾结点,再将尾结点后移。
遍历完成后,利用辅助节点将两个区间拼接,再返回。让我们看下代码:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode partition(ListNode head, int x) { if (head == null || head.next == null) { return head; } // 小于x的节点,开始节点和结束节点 ListNode lessStart = new ListNode(0); ListNode lessEnd = lessStart; // 大于等于x的节点,开始节点和结束节点 ListNode moreStart = new ListNode(0); ListNode moreEnd = moreStart; // 利用current节点扫描 ListNode current = head; while (current != null) { // 小于x的节点 if (current.val < x) { // 添加到相应区间的尾结点,再将尾结点后移 lessEnd.next = current; lessEnd = current; } // 大于等于x的节点 else { // 添加到相应区间的尾结点,再将尾结点后移 moreEnd.next = current; moreEnd = current; } current = current.next; } // 将两个区间拼接 lessEnd.next = moreStart.next; // 需要让最终尾结点指向null,因为该尾结点不一定是原链表尾结点,如果指向别的节点,可能会造成循环链表 moreEnd.next = null; // 返回现在的头结点 return lessStart.next; } }
提交OK,执行用时: 1 ms
,内存消耗: 35.9 MB
。
总结
以上就是这道题目我的解答过程了,不知道大家是否理解了。正如上面所说,针对链接这样的题目,可以借用辅助节点,简化拼接过程,方便使用。
有兴趣的话可以访问我的博客或者关注我的公众号,说不定会有意外的惊喜。
https://death00.github.io/
公众号:健程之道
点击此处留言