【LintCode 简单】96. 链表划分

朱雀 2022-06-01 09:52 199阅读 0赞

1.问题描述：

给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。

你应该保留两部分内链表节点原有的相对顺序。

2.样例：

给定链表 1->4->3->2->5->2->null，并且 x=3

返回 1->2->2->4->3->5->null

3.代码：

第一种方法：

"""
    Definition of ListNode
    class ListNode(object):
    
        def __init__(self, val, next=None):
            self.val = val
            self.next = next
    """
    
    
    class Solution:
        """
        @param: head: The first node of linked list
        @param: x: An integer
        @return: A ListNode
        """
        def partition(self, head, x):
            # write your code here
            if head is None:  
                return head  
            # 新建两个节点  
            first = ListNode(-1)  
            second = ListNode(-1)  
            cur1, cur2 = first, second  
            # 遍历原始链表  
            while head:  
                if head.val < x:  
                    cur1.next = head  
                    head = head.next  
                    cur1 = cur1.next  
                else:  
                    cur2.next = head  
                    head = head.next  
                    cur2 = cur2.next  
            # 合并  
            cur1.next = second.next  
            cur2.next = None  
            return first.next

第二种方法：

"""
    Definition of ListNode
    class ListNode(object):
    
        def __init__(self, val, next=None):
            self.val = val
            self.next = next
    """
    
    
    class Solution:
        """
        @param: head: The first node of linked list
        @param: x: An integer
        @return: A ListNode
        """
        def partition(self, head, x):
            # write your code here
            if head is None:
                return None
            elif head.next is None:
                return head
            else:
                tail=head
                count=1
                while tail.next:
                    tail=tail.next
                    count+=1
                pre=ListNode(0)
                cur=head
                pre.next=cur
                i=0
                fg=True
                while i<count:
                    if cur.val>=x:
                        tail.next=cur
                        pre.next=cur.next
                        tail=cur
                        if fg:
                            head=head.next
                        tail.next=None
                        cur=pre.next
                    else:
                        fg=False
                        pre=pre.next
                        cur=cur.next
                    i+=1
                return head