86. 分隔链表

基本思路

感觉和快速排序中的Partition很接近, 相比数组的分割, 链表可以直接分别储存左支和右支, 在思路上会清晰很多.

而如果依然是采用快排的方式, 那么就需要在交换两个节点时依次替换所有关联节点, 效率不如前者.

Java代码

class Solution {
  public ListNode partition(ListNode head, int x) {
    ListNode smallHead = new ListNode(0);
    ListNode smallEnd = smallHead;
    ListNode largeHead = new ListNode(0);
    ListNode largeEnd = largeHead;
    ListNode currentNode = head;
    while (currentNode != null) {
      if (currentNode.val < x) {
        smallEnd.next = currentNode;
        smallEnd = smallEnd.next;
      } else {
        largeEnd.next = currentNode;
        largeEnd = largeEnd.next;
      }
      currentNode = currentNode.next;
    }
    largeEnd.next = null;
    smallEnd.next = largeHead.next;
    return smallHead.next;
  }
}

测试代码:

public static void main(String[] args) {
  Solution solution = new PartitionList().new Solution();
  ListNode n1 = new ListNode(1);
  ListNode n2 = new ListNode(2);
  ListNode n3 = new ListNode(3);
  ListNode n4 = new ListNode(4);
  n4.next = n3;
  n3.next = n1;
  n1.next = n2;
  System.out.println(solution.partition(n4, 2));
}

复杂度

• 时间复杂度为$O(n)$

  遍历了链表一次

• 空间复杂度为$O(1)$

解答结果

执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:37.9 MB,击败了35.15% 的Java用户

note

这是一篇从Hexo迁移的文章，创建于2021-01-03 17:35:08