Leetcode-086-分割链表

Leetcode-086-分隔链表

题目描述

给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例：

输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5

思路一 ： 模拟

• 直观来说我们只需维护两个链表 small 和 large 即可，small 链表按顺序存储所有小于 x 的节点，large 链表按顺序存储所有大于等于 x 的节点。

• 遍历完原链表后，我们只要将 small 链表尾节点指向 large 链表的头节点即能完成对链表的分隔。

算法具体

1. 设置两个链表的哑节点，smallHead和largeHead , 他们的next 指针指向链表的头结点，这么做的目的是为了更方便的处理头结点为空的边界条件
2. 同时设置 small和 large节点指向当前链表的末尾节点
3. 开始时，smallHead = small ,largeHead = large
   • 随后，从前往后遍历链表，判断当前链表的值是否小于x,如果小于就将small 的next指向该节点
   • 否则就将large的next指向该节点
4. 遍历结束后，将large的next指针置空 , 这是因为当前节点复用的是原链表的节点，而它的next 可能指向一个小于x的节点，我们需要切断这个引用
5. 同时将small 的next 指向largeHead 的 next指针指向的节点，即真正意义上的large链表的头结点。
6. 最后返回smallHead的next就是我们需要的答案。

/**
 * 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) {
        // 1. 设置两个链表的头结点 和 双指针
        ListNode small = new ListNode(0);
        ListNode smallHead = small;
        ListNode large = new ListNode(0);
        ListNode largeHead = large;

        // 2. 遍历链表 ： 按大小进行拆分
        while(head != null){
            // 2.1 比大小，并且两个指针各往前走一步
            if(head.val < x){
                small.next = head;
                small = small.next;
            }else{
                large.next = head;
                large = large.next;
            }
            // 2.2 遍历下一个节点
            head = head.next;
        }
        // 3. 将两个链表进行拼接
        large.next = null;                      // 当前节点复用的是原链表的节点，而它的next 可能指向一个小于x的节点
        small.next = largeHead.next;

        // 4. 最后返回整个新链表的头结点
        return smallHead.next;   
    }
}

复杂度分析

• 时间复杂度: O(n)，其中 n 是原链表的长度。我们对该链表进行了一次遍历。
• 空间复杂度: O(1)。

打赏