LeetCode_双指针_中等_86.分隔链表

短命女 2023-10-12 10:26 14阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。**你应当保留两个分区中每个节点的初始相对位置。**

**示例 1：**

![在这里插入图片描述][784a60c246bc40559f5852db0b55c9ff.png]

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

**示例 2：**  
输入：head = \[2,1\], x = 2  
输出：\[1,2\]

**提示：**  
链表中节点的数目在范围 \[0, 200\] 内  
\-100 <= Node.val <= 100  
\-200 <= x <= 200

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/partition-list

## 2.思路 ##

（1）双指针  
参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————双指针
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode partition(ListNode head, int x) {
        
            ListNode small = new ListNode(0);
            ListNode smallHead = small;
            ListNode large = new ListNode(0);
            ListNode largeHead = large;
            while (head != null) {
        
                if (head.val < x) {
        
                    small.next = head;
                    small = small.next;
                } else {
        
                    large.next = head;
                    large = large.next;
                }
                head = head.next;
            }
            large.next = null;
            //将两个链表进行拼接
            small.next = largeHead.next;
            return smallHead.next;
        }
    }

[784a60c246bc40559f5852db0b55c9ff.png]: https://img-blog.csdnimg.cn/784a60c246bc40559f5852db0b55c9ff.png
[Link 1]: https://leetcode.cn/problems/partition-list/solution/fen-ge-lian-biao-by-leetcode-solution-7ade/