美文网首页算法
86. 分隔链表

86. 分隔链表

作者: crazyfox | 来源:发表于2021-09-12 19:41 被阅读0次

86. 分隔链表

难度中等455 收藏 分享 切换为英文 接收动态 反馈

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

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

示例 1:

image

<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgba(var(--dsw-fill-tertiary-rgba)); padding: 10px 15px; color: rgba(var(--grey-9-rgb),1); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]
</pre>

示例 2:

<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgba(var(--dsw-fill-tertiary-rgba)); padding: 10px 15px; color: rgba(var(--grey-9-rgb),1); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">输入:head = [2,1], x = 2
输出:[1,2]
</pre>

提示:

  • 链表中节点的数目在范围 [0, 200]
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

思路:
创建左右两个虚拟头节点,遍历源链表,>=x的,添加到右边,<x的添加到左边

/**
 * 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 lhead = new ListNode(0);
        ListNode lTail = lhead;
        ListNode rhead = new ListNode(0);
        ListNode rTail = rhead;

        while(head !=null){
            if(head.val < x){
                lTail.next = head;
                lTail = head;
            }else{
                rTail.next = head;
                rTail = head;               
            }
            head = head.next;
        }
        rTail.next = null;
        lTail.next = rhead.next;
        return lhead.next;
    }
}

相关文章

  • 86. 分隔链表

    86. 分隔链表[https://leetcode-cn.com/problems/partition-list/...

  • 86. 分隔链表

    86. 分隔链表[https://leetcode.cn/problems/partition-list/] 给你...

  • 力扣每日一题:86.分隔链表 创建大小链表与寻找第一个链表头两种

    86.分隔链表[https://leetcode-cn.com/problems/partition-list/s...

  • 86. 分隔链表

    86. 分隔链表 问题 给定一个链表和一个特定值 ,对链表进行分隔,使得所有小于 的节点都在大于或等于的节点之前。...

  • 86. 分隔链表

    双指针法: 直觉我们可以用两个指针pbig 和 psmall 来追踪上述的两个链表。两个指针可以用于分别创建两个链...

  • 86. 分隔链表

    原题 https://leetcode-cn.com/problems/partition-list/submis...

  • 86. 分隔链表

    https://leetcode-cn.com/problems/partition-list/solution/...

  • 86. 分隔链表

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

  • LeetCode 86. 分隔链表

    86. 分隔链表 给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点...

  • 每日一题2. 分隔链表

    86. 分隔链表 给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点...

网友评论

    本文标题:86. 分隔链表

    本文链接:https://www.haomeiwen.com/subject/bxptgltx.html