美文网首页
leetcode 86. 分隔链表

leetcode 86. 分隔链表

作者: topshi | 来源:发表于2019-05-30 15:24 被阅读0次

题目描述

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
相关话题: 链表、双指针   难度: 中等

示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

思路:
思路其实和荷兰国旗问题的partition差不多,只是有些边界问题需要注意。

  • 定义一个left指针指向小于x的节点的部分的最后一个节点;p指针遍历链表
  • 如果p.next指向节点的值小于x,那么需要将其脱离并插入到left的后面,left后移一个节点;
  • 一般地,p指针不需要动,因为脱离了p.next后,p的下一个节点更新了。然而,有个边界问题是left更新后(left = left.next),pleft的左边了,其实left左边的节点都是遍历过了的,p应该向前移动。

    如上图,节点1插入到left的后面,left后移一位,p应该跟上。
  • p.next = null结束
/**
 * 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) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        ListNode left = head;
        for(ListNode p = head;p.next != null;){
            if(p.next.val < x){
                ListNode tmp = p.next;
                p.next = tmp.next;
                tmp.next = left.next;
                left.next = tmp;
                left = left.next;
                p = p.next == left?p.next:p;
            }else{
                p = p.next;
            }
        }
        return head.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...

  • LeetCode 86. 分隔链表

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

  • leetcode 86. 分隔链表

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

  • Leetcode归类

    链表: Leetcode-725:分隔链表

  • LeetCode 力扣 86. 分隔链表

    题目描述(中等难度) 题目描述的很难理解,其实回想一下快排就很好理解了。就是快排的分区,将链表分成了两部分,一部分...

  • 86. 分隔链表

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

  • 86. 分隔链表

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

  • 86. 分隔链表

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

网友评论

      本文标题:leetcode 86. 分隔链表

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