086.PartitionList.md

86. Partition List

Problem:

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Solution:

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

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        a = []
        b = []
        if head == None:
            return None
        new_head = head
        while head != None:
            if head.val < x:
                a.append(head.val)
            else:
                b.append(head.val)
            head = head.next
        a.extend(b)
        print(a)
        new_new_head = new_head
        for i in a:
            new_head.val = i
            new_head = new_head.next
        return new_new_head

Solution 2 : Quick Answer

l1 表示小于链表的最后一个位置

l1 链接起所有小于的数

l2 表示大于链表的最后一个位置

l2 连接起所有大于等于的数

h2 是 l2 的头

h1 是 l1 的头

l2.next = None
l1.next = h2 . next
return h1 . next 

def partition(self, head, x):
    h1 = l1 = ListNode(0)
    h2 = l2 = ListNode(0)
    while head:
        if head.val < x:
            l1.next = head
            l1 = l1.next
        else:
            l2.next = head
            l2 = l2.next
        head = head.next
    l2.next = None
    l1.next = h2.next
    return h1.next

Key Point:

怎么连接两个链表