Reorder List

Question

Problem Statement

Given a singly linked list L: L_0→_L_1→…→_L__n-1→L_n,
reorder it to: _L_0→_L__n
L_1→_L__n-1→L_2→_L__n-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

题解1 - 链表长度(TLE)

直观角度来考虑,如果把链表视为数组来处理,那么我们要做的就是依次将下标之和为n的两个节点链接到一块儿,使用两个索引即可解决问题,一个索引指向i, 另一个索引则指向其之后的第n - 2*i个节点(对于链表来说实际上需要获取的是其前一个节点), 直至第一个索引大于第二个索引为止即处理完毕。

既然依赖链表长度信息,那么要做的第一件事就是遍历当前链表获得其长度喽。获得长度后即对链表进行遍历,小心处理链表节点的断开及链接。用这种方法会提示 TLE,也就是说还存在较大的优化空间!

题解2 - 反转链表后归并

既然题解1存在较大的优化空间,那我们该从哪一点出发进行优化呢?擒贼先擒王,题解1中时间复杂度最高的地方在于双重for循环,在对第二个索引进行遍历时,j每次都从i处开始遍历,要是j能从链表尾部往前遍历该有多好啊!这样就能大大降低时间复杂度了,可惜本题的链表只是单向链表... 有什么特技可以在单向链表中进行反向遍历吗?还真有——反转链表!一语惊醒梦中人。

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

class Solution:
    # @param head, a ListNode
    # @return nothing
    def reorderList(self, head):
        if head==None or head.next==None or head.next.next==None: return head

        # break linked list into two equal length
        slow = fast = head                              #快慢指针技巧
        while fast and fast.next:                       #需要熟练掌握
            slow = slow.next                            #链表操作中常用
            fast = fast.next.next
        head1 = head
        head2 = slow.next
        slow.next = None

        # reverse linked list head2
        dummy=ListNode(0); dummy.next=head2             #翻转前加一个头结点
        p=head2.next; head2.next=None                   #将p指向的节点一个一个插入到dummy后面
        while p:                                        #就完成了链表的翻转
            tmp=p; p=p.next                             #运行时注意去掉中文注释
            tmp.next=dummy.next
            dummy.next=tmp
        head2=dummy.next

        # merge two linked list head1 and head2
        p1 = head1; p2 = head2
        while p2:
            tmp1 = p1.next; tmp2 = p2.next
            p1.next = p2; p2.next = tmp1
            p1 = tmp1; p2 = tmp2
"""
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 the linked list.
    @return: nothing
    """
    def reorderList(self, head):
        # write your code here
        if None == head or None == head.next:
            return head

        pfast = head
        pslow = head

        while pfast.next and pfast.next.next:
            pfast = pfast.next.next
            pslow = pslow.next
        pfast = pslow.next
        pslow.next = None

        pnext = pfast.next
        pfast.next = None
        while pnext:
            q = pnext.next
            pnext.next = pfast
            pfast = pnext
            pnext = q

        tail = head
        while pfast:
            pnext = pfast.next
            pfast.next = tail.next
            tail.next = pfast
            tail = tail.next.next
            pfast = pnext
        return head

源码分析

相对于题解1,题解2更多地利用了链表的常用操作如反转、找中点、合并。

  1. 找中点:我在九章算法模板的基础上增加了对head->next的异常检测,增强了鲁棒性。
  2. 反转:非常精炼的模板,记牢!
  3. 合并:也可使用九章提供的模板,思想是一样的,需要注意left, rightdummy三者的赋值顺序,不能更改任何一步。

复杂度分析

找中点一次,时间复杂度近似为 $$O(n)$$. 反转链表一次,时间复杂度近似为 $$O(n/2)$$. 合并左右链表一次,时间复杂度近似为 $$O(n/2)$$. 故总的时间复杂度为 $$O(n)$$.

results matching ""

    No results matching ""