[leetcode题解]143. Reorder List(链表重排序)

leetcode第143题,recorder list,属于linked-list相关的题目。
题目给定一个单链表,然后要求按给定的顺序重新排列所有元素,要求在原地做,而且不能修改节点中的值,只能修改节点的插入顺序。重排序的规则如下示例:

L:a0->a1->a2->a3…..->an
将其修改为L:a0->an->a1->an-1->…

总体的思路主要是:
1.先找到链表的中间节点,然后以中间节点为界将整个链表分成前后两部分。
2.将后半部分链表通过头插的方式进行链表逆置
3.一次交叉插入形成一个新的链表

c++代码如下:

class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == NULL || head->next == NULL)return;
        ListNode *prel = new ListNode(-1);
        ListNode *prer = new ListNode(-1);
        ListNode *res = new ListNode(-1);
        
        //作者:凌风技术站-iaccepted
        //寻找链表的中间节点,并将链表按中间节点一分为二
        prel->next = head;
        ListNode *half = halfNode(head);
        ListNode *t = half;
        half = half->next;
        t->next = NULL;
        
        //将链表的后半部分颠倒
        while(half != NULL)
        {
            ListNode *t = half->next;
            half->next = prer->next;
            prer->next = half;
            half = t;
        }
        
        //按题目要求交叉连接
        ListNode *tail = res;
        ListNode *p = prel->next;
        ListNode *q = prer->next;
        while(p != NULL)
        {
            tail->next = p;
            tail = p;
            p = p->next;
            
            tail->next = q;
            tail = q;
            q = q->next;
        }
        if (q != NULL)tail->next = q;
        else tail->next = NULL;
    }
    
private:
    ListNode *halfNode(ListNode *head)
    {
        if (head == NULL || head->next == NULL)return head;
        ListNode *slow = head;
        ListNode *fast = head->next->next;
        while(fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

python代码如下:

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        :author: 凌风技术站
        """
        if head is None or head.next is None:
            return
        #招链表的中间节点,并将链表一分为二
        mid = self.halfNode(head)
        p = head
        q = mid.next
        mid.next = None
        
        #将后半部分逆置
        rq = ListNode(-1)
        while q is not None:
            t = q.next
            q.next = rq.next
            rq.next = q
            q = t
        q = rq.next
        
        #开始交叉合并前后两部分
        pre = ListNode(-1)
        tail = pre
        
        while q is not None:
            tail.next = p
            p = p.next
            tail = tail.next
            tail.next = q
            q = q.next
            tail = tail.next
        if p is not None:
            tail.next = p
        head = pre.next
            
        
    def halfNode(self, head):
        slow = head
        fast = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

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

本文标题:[leetcode题解]143. Reorder List(链表重排序)

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

相关文章



发表评论

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