六六力扣刷题链表之分隔链表

前言

之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两台晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀

链表

• ​​六六力扣刷题链表之移除链表元素​​
• ​​六六力扣刷题链表之反转链表​​
• ​​六六力扣刷题链表之两两交换链表中的节点​​
• ​​六六力扣刷题链表之合并两个有序链表​​
• ​​六六力扣刷题链表之反转链表 II​​

链表的理论基础

链表的种类主要为：单链表，双链表，循环链表

链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。

链表是如何进行增删改查的。

数组和链表在不同场景下的性能分析。

可以说把链表基础的知识都概括了，但又不像教科书那样的繁琐。

虚拟头结点

链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。

每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。

题目

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

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

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

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

思路

直观来说我们只需维护两个链表 small 和 large 即可，\textit{small}small 链表按顺序存储所有小于 xx 的节点，large 链表按顺序存储所有大于等于 xx 的节点。遍历完原链表后，我们只要将 small 链表尾节点指向large 链表的头节点即能完成对链表的分隔。

为了实现上述思路，我们设 smallHead 和 largeHead 分别为两个链表的哑节点，即它们的 next 指针指向链表的头节点，这样做的目的是为了更方便地处理头节点为空的边界条件。同时设 small 和 large 节点指向当前链表的末尾节点。。随后，从前往后遍历链表，判断当前链表的节点值是否小于 xx，如果小于就将 small 的 next 指针指向该节点，否则将 large 的 next 指针指向该节点。

遍历结束后，我们将 large 的 next 指针置空，这是因为当前节点复用的是原链表的节点，而其 next 指针可能指向一个小于 xx 的节点，我们需要切断这个引用。同时将 small 的 next 指针指向 largeHead 的 next 指针指向的节点，即真正意义上的 large 链表的头节点。最后返回 smallHead 的 next 指针即为我们要求的答案。

题解

package com.six.finger.leetcode.two;

import com.six.finger.leetcode.common.ListNode1;

public class Partition {


    public ListNode1 partition(ListNode1 head, int x) {

        ListNode1 first = new ListNode1(0);

        ListNode1 firstHead = first;

        ListNode1 last = new ListNode1(0);
        ListNode1 lastHead = last;

        while (head != null) {
            if (head.val >= x) {
                last.next = head;
                last = last.next;
            } else {

                first.next = head;
                first = first.next;
            }
            head = head.next;
        }
        last.next = null;
        first.next = lastHead.next;

        return firstHead.next;      

结束