86、分隔链表

leetcode

Created At : 2020-07-26 00:19

Count:350 Views 👀 :

Comment:

86、分隔（二分）链表
1. 示例:

题解

1、尾插法创建子链表

86、分隔（二分）链表

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

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

示例:

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

链接：https://leetcode-cn.com/problems/partition-list

题解

1、尾插法创建子链表

创建两个辅助头结点，将原来的链表按照原始顺序分成两波：

一波是小于目标值的
一波是大于等于目标值的

/**
 * 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) {
        // 链表没有排序
        // 所有小于 x 的节点都在大于或等于 x 的节点之前。
        // 但是仍然需要保证相对顺序
        // case: 空链表
        if (head == null) {
            return head;
        }
        ListNode t,q,p,dummy1,dummy2;
        dummy1 = new ListNode(-1);// 小于目标值的链表
        dummy2 = new ListNode(-1);// 大于或等于目标值的链表
        p = dummy1;
        q = dummy2;
        t = head;
        while(t != null) {
            if (t.val >= x) {
                q.next = t;
                q = t;
                t = t.next; // 
                q.next = null; // 断开后续结点
            }else {
                p.next = t;
                p = t;
                t = t.next;
                p.next = null;// 断开后续结点
            }
        }
        // 拼接链表
        p.next = dummy2.next;

        return dummy1.next;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com