JavaScript分隔鏈表問題怎么解決

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

原題

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

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

示例:

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

解題

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

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

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

遍歷完成后，利用輔助節(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é)點
        ListNode lessStart = new ListNode(0);
        ListNode lessEnd = lessStart;
        // 大于等于x的節(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) {
                // 添加到相應區(qū)間的尾結點，再將尾結點后移
                lessEnd.next = current;
                lessEnd = current;
            }
            // 大于等于x的節(jié)點
            else {
                // 添加到相應區(qū)間的尾結點，再將尾結點后移
                moreEnd.next = current;
                moreEnd = current;
            }

            current = current.next;
        }

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

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

到此，關于“JavaScript分隔鏈表問題怎么解決”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>