86_分隔链表

类型：链表

• 86. 分隔链表 💛

  https://leetcode-cn.com/problems/partition-list/

  ❓ 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。

  💡 模拟

  我们需要维护两个链表，一个专门存储小结点，一个专门存储大结点，然后在将两者衔接。

  为了实现上述思路，我们设 smallHead 和 largeHead 分别为两个链表的哑节点，即它们的 next 指针指向链表的头节点，这样做的目的是为了更方便地处理头节点为空的边界条件。

  # 官方实现
  class Solution {
      public ListNode partition(ListNode head, int x) {
          ListNode small = new ListNode(0);
          ListNode smallHead = small;
          ListNode large = new ListNode(0);
          ListNode largeHead = large;
          while (head != null) {
              if (head.val < x) {
                  small.next = head;
                  small = small.next;
              } else {
                  large.next = head;
                  large = large.next;
              }
              head = head.next;
          }
          large.next = null;
          small.next = largeHead.next;
          return smallHead.next;
      }
  }

  # 我的实现，没有用到虚拟头结点
  class Solution:
      def partition(self, head: ListNode, x: int) -> ListNode:
          lList = None
          gList = None
          lp = lList
          gp = gList
          while head:
              if head.val < x:
                  if not lp:
                      lList = head
                      lp = lList
                  else:
                      lp.next = head
                      lp = lp.next
              else:
                  if not gp:
                      gList = head
                      gp = gList
                  else:
                      gp.next = head
                      gp = gp.next
              head = head.next
          if gp:
              gp.next = None
          if lp:
              lp.next = gList
              return lList
          else:
              return gList

  时间复杂度：O(n)，空间复杂度：O(1)