[leetcode题解]86.Partition List(链表分割)

leetcode第86题,partition-list,是一个关于链表分割的题目。题目给定一个单链表和一个数x,要求链表中节点val小于x的节点全部在左边,而大于等于x的节点全部在右边,而且左右两边中的元素分别保持在原链表中的相对位置。总体来说就类似于快排中的partition部分。所以这个的实现可以直接使用快排的中partition方法直接在单链表上更换节点的值就好。

这里使用最原始的思路,就是把两部分分别取出来,然后链接起来达到要求的效果,取出来的时候由于要求保持相对位置,所以使用单链表尾插法,最后两部分相连。

c++代码

class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
    //将两部分分别链接出来,用lh记录左边部分,gh记录右边部分
        ListNode *lh = new ListNode(-1);
        ListNode *gh = new ListNode(-1);
        
        ListNode *p = head, *tailL = lh, *tailG = gh;
        while(p != NULL)
        {
            if (p->val < x)
            {
                tailL->next = p;
                tailL = tailL->next;
            }
            else
            {
                tailG->next = p;
                tailG = tailG->next;
            }
            
            p = p->next;
        }

        //最后两部分链接起来即可
        tailL->next = NULL;
        tailG->next = NULL;
        tailL->next = gh->next;
        return lh->next;
    }
};

python代码:

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        la = ListNode(-1)
        lb = ListNode(-1)
        
        taila, tailb = la, lb
        
        while head is not None:
            t = head.next
            if head.val < x:
                head.next = taila.next
                taila.next = head
                taila = head
            else:
                head.next = tailb.next
                tailb.next = head
                tailb = head
            head = t
        
        taila.next = lb.next
        return la.next

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]86.Partition List(链表分割)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/82.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注