建站
咨詢
售后
建站咨詢
新聞中心
這篇文章主要介紹“JavaScript分隔鏈表問題怎么解決”，在日常操作中，相信很多人在JavaScript分隔鏈表問題怎么解決問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”JavaScript分隔鏈表問題怎么解決”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！
光澤網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián),光澤網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為光澤成百上千提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)公司要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的光澤做網(wǎng)站的公司定做！
原題
給定一個(gè)鏈表和一個(gè)特定值 x，對(duì)鏈表進(jìn)行分隔，使得所有小于 x 的節(jié)點(diǎn)都在大于或等于 x 的節(jié)點(diǎn)之前。
你應(yīng)當(dāng)保留兩個(gè)分區(qū)中每個(gè)節(jié)點(diǎn)的初始相對(duì)位置。
示例:
輸入: head = 1->4->3->2->5->2, x = 3
輸出: 1->2->2->4->3->5解題
題目很好理解，重點(diǎn)在于區(qū)分大于等于和小于目標(biāo)值的節(jié)點(diǎn)，判斷其實(shí)是很簡(jiǎn)單的，主要在于如何拼接鏈表，以及最終如何返回。
我發(fā)現(xiàn)，針對(duì)鏈表拼接的這種題目，常?？梢酝ㄟ^添加輔助節(jié)點(diǎn)（輔助頭結(jié)點(diǎn)或者輔助尾結(jié)點(diǎn)）來(lái)簡(jiǎn)化拼接操作。
這道題的話，需要針對(duì)兩個(gè)區(qū)間都添加輔助頭結(jié)點(diǎn)和尾結(jié)點(diǎn)，然后利用一個(gè) current 節(jié)點(diǎn)進(jìn)行遍歷，掃描到大于等于目標(biāo)值的節(jié)點(diǎn)，添加到相應(yīng)區(qū)間的尾結(jié)點(diǎn)，再將尾結(jié)點(diǎn)后移；小于目標(biāo)值的節(jié)點(diǎn)，添加到相應(yīng)區(qū)間的尾結(jié)點(diǎn)，再將尾結(jié)點(diǎn)后移。
遍歷完成后，利用輔助節(jié)點(diǎn)將兩個(gè)區(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é)點(diǎn)，開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)
ListNode lessStart = new ListNode(0);
ListNode lessEnd = lessStart;
// 大于等于x的節(jié)點(diǎn)，開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)
ListNode moreStart = new ListNode(0);
ListNode moreEnd = moreStart;
// 利用current節(jié)點(diǎn)掃描
ListNode current = head;
while (current != null) {
// 小于x的節(jié)點(diǎn)
if (current.val < x) {
// 添加到相應(yīng)區(qū)間的尾結(jié)點(diǎn)，再將尾結(jié)點(diǎn)后移
lessEnd.next = current;
lessEnd = current;
}
// 大于等于x的節(jié)點(diǎn)
else {
// 添加到相應(yīng)區(qū)間的尾結(jié)點(diǎn)，再將尾結(jié)點(diǎn)后移
moreEnd.next = current;
moreEnd = current;
}
current = current.next;
}
// 將兩個(gè)區(qū)間拼接
lessEnd.next = moreStart.next;
// 需要讓最終尾結(jié)點(diǎn)指向null，因?yàn)樵撐步Y(jié)點(diǎn)不一定是原鏈表尾結(jié)點(diǎn)，如果指向別的節(jié)點(diǎn)，可能會(huì)造成循環(huán)鏈表
moreEnd.next = null;
// 返回現(xiàn)在的頭結(jié)點(diǎn)
return lessStart.next;
}
}
提交OK，執(zhí)行用時(shí)：1 ms，內(nèi)存消耗：35.9 MB。
到此，關(guān)于“JavaScript分隔鏈表問題怎么解決”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！
分享題目：JavaScript分隔鏈表問題怎么解決
URL鏈接：http://www.dlmjj.cn/article/jepdcs.html
