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