這篇文章主要介紹“JavaScript分隔鏈表問題怎么解決”，在日常操作中，相信很多人在JavaScript分隔鏈表問題怎么解決問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”JavaScript分隔鏈表問題怎么解決”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

光澤網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián),光澤網(wǎng)站設(shè)計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為光澤成百上千提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)公司要多少錢，請找那個售后服務(wù)好的光澤做網(wǎng)站的公司定做！

原題

給定一個鏈表和一個特定值 x，對鏈表進行分隔，使得所有小于 x 的節(jié)點都在大于或等于 x 的節(jié)點之前。

你應(yīng)當(dāng)保留兩個分區(qū)中每個節(jié)點的初始相對位置。

示例:

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

解題

題目很好理解，重點在于區(qū)分大于等于和小于目標(biāo)值的節(jié)點，判斷其實是很簡單的，主要在于如何拼接鏈表，以及最終如何返回。

我發(fā)現(xiàn)，針對鏈表拼接的這種題目，常?？梢酝ㄟ^添加輔助節(jié)點（輔助頭結(jié)點或者輔助尾結(jié)點）來簡化拼接操作。

這道題的話，需要針對兩個區(qū)間都添加輔助頭結(jié)點和尾結(jié)點，然后利用一個 current 節(jié)點進行遍歷，掃描到大于等于目標(biāo)值的節(jié)點，添加到相應(yīng)區(qū)間的尾結(jié)點，再將尾結(jié)點后移；小于目標(biāo)值的節(jié)點，添加到相應(yīng)區(qū)間的尾結(jié)點，再將尾結(jié)點后移。

遍歷完成后，利用輔助節(jié)點將兩個區(qū)間拼接，再返回。讓我們看下代碼：

/**
* 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的節(jié)點，開始節(jié)點和結(jié)束節(jié)點
       ListNode lessStart = new ListNode(0);
       ListNode lessEnd = lessStart;
       // 大于等于x的節(jié)點，開始節(jié)點和結(jié)束節(jié)點
       ListNode moreStart = new ListNode(0);
       ListNode moreEnd = moreStart;

       // 利用current節(jié)點掃描
       ListNode current = head;
       while (current != null) {
           // 小于x的節(jié)點
           if (current.val < x) {
               // 添加到相應(yīng)區(qū)間的尾結(jié)點，再將尾結(jié)點后移
               lessEnd.next = current;
               lessEnd = current;
           }
           // 大于等于x的節(jié)點
           else {
               // 添加到相應(yīng)區(qū)間的尾結(jié)點，再將尾結(jié)點后移
               moreEnd.next = current;
               moreEnd = current;
           }

           current = current.next;
       }

        // 將兩個區(qū)間拼接
       lessEnd.next = moreStart.next;
        // 需要讓最終尾結(jié)點指向null，因為該尾結(jié)點不一定是原鏈表尾結(jié)點，如果指向別的節(jié)點，可能會造成循環(huán)鏈表
       moreEnd.next = null;
        // 返回現(xiàn)在的頭結(jié)點
       return lessStart.next;
   }
}

提交OK，執(zhí)行用時：1 ms，內(nèi)存消耗：35.9 MB。

到此，關(guān)于“JavaScript分隔鏈表問題怎么解決”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>
分享標(biāo)題：JavaScript分隔鏈表問題怎么解決
網(wǎng)站地址：http://weahome.cn/article/jepdcs.html