【Leetcode 程序员面试金典 02.04】 —— 分割链表|双指针

面试题02.04. 分割链表

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

你不需要 保留 每个分区中各节点的初始相对位置。

示例1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

题目分析

我们可以使用双指针解决本题，定义两个链表 small 和 big 即可，small 链表按顺序存储所有小于 x 的节点，big 链表按顺序存储所有大于等于 x 的节点。

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

双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息

经典双指针的数组遍历，更多案例可见 Leetcode 双指针详解

/**
 * 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) {
    	// 新建起始节点，方便处理头节点为空的边界条件
		ListNode small = new ListNode(0), big = new ListNode(0);
		ListNode smallHead = small, bigHead = big;
		while(head != null){
			// 判断值以决定加入small/big链表
			if (head.val < x) {
				small.next = head;
				small = small.next;
			} else {
				big.next = head;
				big = big.next;
			}
			head = head.next;
		}
		// 尾结点
		big.next = null;
		// 小值链表接大值链表
		small.next = bigHead.next;
		return smallHead.next;
    }
}