Question

面试题 02.04. 分割链表

English Version

题目描述

给你一个链表的头节点 head 和一个特定值_ _x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

 

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

 

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

解法

方法一：拼接链表

我们创建两个链表 $left$ 和 $right$，分别用于存储小于 $x$ 的节点和大于等于 $x$ 的节点。

然后我们用两个指针 $p1$ 和 $p2$ 分别指向 $left$ 和 $right$ 的最后一个节点，初始时 $p1$ 和 $p2$ 都指向一个虚拟头节点。

接下来我们遍历链表 $head$，如果当前节点的值小于 $x$，我们就将当前节点添加到 $left$ 链表的末尾，即 $p1.next = head$，然后令 $p1 = p1.next$；否则我们就将当前节点添加到 $right$ 链表的末尾，即 $p2.next = head$，然后令 $p2 = p2.next$。

遍历结束后，我们将 $left$ 链表的尾节点指向 $right$ 链表的第一个有效节点，即 $p1.next = right.next$，然后将 $right$ 链表的尾节点指向空节点，即 $p2.next = null$。

最后我们返回 $left$ 链表的第一个有效节点。

时间复杂度 $O(n)$，其中 $n$ 是链表的长度。空间复杂度 $O(1)$。

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, x):
#     self.val = x
#     self.next = None


class Solution:
  def partition(self, head: ListNode, x: int) -> ListNode:
    left, right = ListNode(0), ListNode(0)
    p1, p2 = left, right
    while head:
      if head.val < x:
        p1.next = head
        p1 = p1.next
      else:
        p2.next = head
        p2 = p2.next
      head = head.next
    p1.next = right.next
    p2.next = None
    return left.next

/**
 * 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) {
    ListNode left = new ListNode(0);
    ListNode right = new ListNode(0);
    ListNode p1 = left;
    ListNode p2 = right;
    for (; head != null; head = head.next) {
      if (head.val < x) {
        p1.next = head;
        p1 = p1.next;
      } else {
        p2.next = head;
        p2 = p2.next;
      }
    }
    p1.next = right.next;
    p2.next = null;
    return left.next;
  }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* partition(ListNode* head, int x) {
    ListNode* left = new ListNode(0);
    ListNode* right = new ListNode(0);
    ListNode* p1 = left;
    ListNode* p2 = right;
    for (; head; head = head->next) {
      if (head->val < x) {
        p1->next = head;
        p1 = p1->next;
      } else {
        p2->next = head;
        p2 = p2->next;
      }
    }
    p1->next = right->next;
    p2->next = nullptr;
    return left->next;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
  left, right := &ListNode{}, &ListNode{}
  p1, p2 := left, right
  for ; head != nil; head = head.Next {
    if head.Val < x {
      p1.Next = head
      p1 = p1.Next
    } else {
      p2.Next = head
      p2 = p2.Next
    }
  }
  p1.Next = right.Next
  p2.Next = nil
  return left.Next
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 *   }
 * }
 */

function partition(head: ListNode | null, x: number): ListNode | null {
  const [left, right] = [new ListNode(), new ListNode()];
  let [p1, p2] = [left, right];
  for (; head; head = head.next) {
    if (head.val < x) {
      p1.next = head;
      p1 = p1.next;
    } else {
      p2.next = head;
      p2 = p2.next;
    }
  }
  p1.next = right.next;
  p2.next = null;
  return left.next;
}