力扣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/