【LintCode 简单】96. 链表划分-白红宇

【LintCode 简单】96. 链表划分

阅读量：4088 次

发布时间：2019-05-25

本文共 2117 字，大约阅读时间需要 7 分钟。

1.问题描述：

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

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

2.样例：

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

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

3.代码：

第一种方法：

"""Definition of ListNodeclass 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 ListNodeclass 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
    
     =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