資訊專欄INFORMATION COLUMN
摘要：當(dāng)前節(jié)點(diǎn)的前一個節(jié)點(diǎn)插入位置的前一個節(jié)點(diǎn)，以及記錄初始位置的節(jié)點(diǎn)。當(dāng)發(fā)現(xiàn)一個需要交換的節(jié)點(diǎn)時，先獲得這個節(jié)點(diǎn)，然后將指向節(jié)點(diǎn)的后一個節(jié)點(diǎn)。最后將兩個鏈表連接。代碼相比于第一種更加清晰一些。
題目要求
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
將小于x的值放在前面，大于等于x的值放在后面，移動的過程中不改變數(shù)字之間的相對順序。
思路一：移動節(jié)點(diǎn)該思路需要我們記錄3個節(jié)點(diǎn)。當(dāng)前節(jié)點(diǎn)的前一個節(jié)點(diǎn)currentPrev,插入位置的前一個節(jié)點(diǎn)prev，以及記錄初始位置的節(jié)點(diǎn)start。當(dāng)發(fā)現(xiàn)一個需要交換的節(jié)點(diǎn)時，先獲得這個節(jié)點(diǎn)，然后將currentPrev指向節(jié)點(diǎn)的后一個節(jié)點(diǎn)。之后將當(dāng)前的節(jié)點(diǎn)插入到prev之后。代碼如下：
public ListNode partition(ListNode head, int x) {
if(head==null || head.next==null){
return head;
}
ListNode start = new ListNode(0);
ListNode prev = new ListNode(0);
ListNode currentPrev = new ListNode(0);
start.next = prev;
prev.next = head;
currentPrev.next = head;
while(currentPrev.next!=null && currentPrev.next.val
思路二：使用兩個鏈表
我們設(shè)置兩個頭指針當(dāng)做兩個鏈表，當(dāng)遇到的數(shù)值小于x，則加入第一個鏈表，否則加入第二個鏈表。最后將兩個鏈表連接。代碼相比于第一種更加清晰一些。
public ListNode partition2(ListNode head, int x) {
if (head == null || head.next == null) return head;
ListNode dummy1 = new ListNode(0);
ListNode dummy2 = new ListNode(0);
ListNode curr = head, first = dummy1, second = dummy2;
while (curr != null) {
if (curr.val < x) {
first.next = curr;
first = first.next;
} else {
second.next = curr;
second = second.next;
}
curr = curr.next;
}
first.next = dummy2.next;
second.next = null;
return dummy1.next;
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/67328.html
Problem Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in ea...
Problem A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers represe...
摘要：新建兩個鏈表，分別存和的結(jié)點(diǎn)。令頭結(jié)點(diǎn)分別叫作和，對應(yīng)的指針分別叫作和。然后遍歷，當(dāng)小于的時候放入，否則放入。最后，讓較小值鏈表尾結(jié)點(diǎn)指向較大值鏈表頭結(jié)點(diǎn)，再讓較大值鏈表尾結(jié)點(diǎn)指向。 Problem Given a linked list and a value x, partition it such that all nodes less than x come before no...
摘要：深度優(yōu)先搜素復(fù)雜度時間空間思路因為我們要返回所有可能的分割組合，我們必須要檢查所有的可能性，一般來說這就要使用，由于要返回路徑，仍然是典型的做法遞歸時加入一個臨時列表，先加入元素，搜索完再去掉該元素。 Palindrome Partitioning Given a string s, partition s such that every substring of the parti...
閱讀 1781·2021-10-13 09:39
閱讀 3224·2021-10-12 10:11
閱讀 612·2021-09-28 09:36
閱讀 2750·2019-08-30 15:55
閱讀 1466·2019-08-30 13:04
閱讀 690·2019-08-29 17:08
閱讀 1979·2019-08-29 14:14
閱讀 3478·2019-08-28 18:23
