力扣86——分隔鏈表
- 2019 年 12 月 31 日
- 筆記
原題
給定一個鏈表和一個特定值 x,對鏈表進行分隔,使得所有小於 x 的節點都在大於或等於 x 的節點之前。
你應當保留兩個分區中每個節點的初始相對位置。
示例:
輸入: head = 1->4->3->2->5->2, x = 3 輸出: 1->2->2->4->3->5
原題url:https://leetcode-cn.com/problems/partition-list/
解題
題目很好理解,重點在於區分大於等於和小於目標值的節點,判斷其實是很簡單的,主要在於如何拼接鏈表,以及最終如何返回。
我發現,針對鏈表拼接的這種題目,常常可以通過添加輔助節點(輔助頭結點或者輔助尾結點)來簡化拼接操作。
這道題的話,需要針對兩個區間都添加輔助頭結點和尾結點,然後利用一個 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
。
總結
以上就是這道題目我的解答過程了,不知道大家是否理解了。正如上面所說,針對鏈接這樣的題目,可以借用輔助節點,簡化拼接過程,方便使用。
有興趣的話可以訪問我的部落格或者關注我的公眾號,說不定會有意外的驚喜。
https://death00.github.io/