JavaScript分隔链表问题怎么解决

这篇文章主要介绍“JavaScript分隔链表问题怎么解决”，在日常操作中，相信很多人在JavaScript分隔链表问题怎么解决问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”JavaScript分隔链表问题怎么解决”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

光泽网站建设公司创新互联,光泽网站设计制作，有大型网站制作公司丰富经验。已为光泽成百上千提供企业网站建设服务。企业网站搭建\成都外贸网站建设公司要多少钱，请找那个售后服务好的光泽做网站的公司定做！

原题

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

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

示例:

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

解题

题目很好理解，重点在于区分大于等于和小于目标值的节点，判断其实是很简单的，主要在于如何拼接链表，以及最终如何返回。

我发现，针对链表拼接的这种题目，常常可以通过添加辅助节点（辅助头结点或者辅助尾结点）来简化拼接操作。

这道题的话，需要针对两个区间都添加辅助头结点和尾结点，然后利用一个 current 节点进行遍历，扫描到大于等于目标值的节点，添加到相应区间的尾结点，再将尾结点后移；小于目标值的节点，添加到相应区间的尾结点，再将尾结点后移。

遍历完成后，利用辅助节点将两个区间拼接，再返回。让我们看下代码：

/**
* 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 || head.next == null) {
           return head;
       }

       // 小于x的节点，开始节点和结束节点
       ListNode lessStart = new ListNode(0);
       ListNode lessEnd = lessStart;
       // 大于等于x的节点，开始节点和结束节点
       ListNode moreStart = new ListNode(0);
       ListNode moreEnd = moreStart;

       // 利用current节点扫描
       ListNode current = head;
       while (current != null) {
           // 小于x的节点
           if (current.val < x) {
               // 添加到相应区间的尾结点，再将尾结点后移
               lessEnd.next = current;
               lessEnd = current;
           }
           // 大于等于x的节点
           else {
               // 添加到相应区间的尾结点，再将尾结点后移
               moreEnd.next = current;
               moreEnd = current;
           }

           current = current.next;
       }

        // 将两个区间拼接
       lessEnd.next = moreStart.next;
        // 需要让最终尾结点指向null，因为该尾结点不一定是原链表尾结点，如果指向别的节点，可能会造成循环链表
       moreEnd.next = null;
        // 返回现在的头结点
       return lessStart.next;
   }
}

提交OK，执行用时：1 ms，内存消耗：35.9 MB。

到此，关于“JavaScript分隔链表问题怎么解决”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注创新互联网站，小编会继续努力为大家带来更多实用的文章！

文章题目：JavaScript分隔链表问题怎么解决
文章出自：http://6mz.cn/article/jepdcs.html