【数据结构和算法】四指针解决

四指针解决

在算法中双指针我们经常听过，但四指针还是比较少的，四指针顾名思义就是使用4个指针来解决。

这题是让把节点值小于x的节点都放到前面，最简单的一种解决方式就是把原链表的节点分隔为两个链表，其中一个链表节点的值都是小于x的，另一个链表节点的值都是大于或等于x的，最后再把这两个链表合并即可。这里要使用四个指针，其中两个指向小的链表，两个指向大的链表，原理如下图所示

最后我们再来看下代码

public ListNode partition(ListNode head, int x) {
    //小链表的头
    ListNode smallHead = new ListNode(0);
    //大链表的头
    ListNode bigHead = new ListNode(0);
    //小链表的尾
    ListNode smallTail = smallHead;
    //大链表的尾
    ListNode bigTail = bigHead;
    //遍历head链表
    while (head != null) {
        if (head.val < x) {
            //如果当前节点的值小于x，则把当前节点挂到小链表的后面
            smallTail = smallTail.next = head;
        } else {//否则挂到大链表的后面
            bigTail = bigTail.next = head;
        }

        //继续循环下一个结点
        head = head.next;
    }
    //最后再把大小链表拼接在一块即可。
    smallTail.next = bigHead.next;
    bigTail.next = null;
    return smallHead.next;
}

看一下运行结果

截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解