USYD COMP2123 Linked List tutori

这周的知识点

了解以下数据结构的实现, time and space constraint

• array implementation of a list

• singly and doubly linked list

• doubly linked list Stack and Queue

• adv singly linked list stack and queue

python里的run time和function call测试方法

Tutorial

Q3 : Given a singly linked list, traverse the elements of the list in reverse order.

• Design an algorithm that uses O(1) extra space.

首先我们需要了解题意, 是否真的要把linked list反过来.

比如 1->2->3 经过处理后变成 3->2->1.

如果只能使用O(1)的空间, 那么我们除了已经给的list的空间没有更多的地方来存储信息, 那么免不了对原本linkedlist的改动, 也就是

改变node之间next的指向.

O(1)的方法 有iterative和recursive两种解法, 推荐了解iterasive的写法.

在这之前, 先写一个helper function print_linkedlist(head)来帮忙检验. 我们默认print_linkedlist是时间O(n)空间O(1)的.

def print_linkedlist(head):

    node = head

    while(node):

        print(node.value) #traversed

        node = node.next

Iterasive method

def reverseList(head):

    current = head

    prev = None

    while(current):



        curr_next = current.next #先存next, 下一步要走的点

        current.next = prev # **改变当前点的next位置. 反转的一步!**

        prev = current #更新prev称为当前点.

        current = curr_next #更新当前点为next, 下一步要走的点.

    #理解视频: https://www.youtube.com/watch?v=sYcOK51hl-A

    old_last_node = prev

    return old_last_node

print_linkedlist(reverseList(head))

Recursive method

def reverseList(head):

    """

    return the new head with the reversed linkedlist

    """

    if head==None or head.next==None:



        return head

    old_second = self.reverseList(head.next)

    head.next.next = head

    head.next=None



    return old_second

print_linkedlist(reverseList(head))

• Design an algorithm that uses O(sqrt(n)) extra space.

因为题目要求仅仅是reversely traverse, 有多余位置存储信息的话, 我们就可以事实上不改变node之间的联系了.

def reverse_sqrt_n(head):

    # 为了方便描述 记 K = sqrt(n)

    # # -------第一步: 找到list的长度------

    # 假设我们不知道这个list有多长, 我们首先需要获取长度信息.

    n=0

    node=head

    while node:

        n+=1

        node=node.next

    #to know how long is our linked list, time O(n), space O(1)

    k=int(n**.5)+1  #确定sqrt(n)的大小

    # 到这一步为止 time用了n, space用了1

    # ---------第二步: 存储每第K个node位置-------

    # 存储每第sqrt(k)个node

    # 一共有 k/sqrt(k)=sqrt(k)次操作, 存好了以后会使用sqrt(k)space.

    i=0

    node=self

    lsa=[node]

    node_stored_position_sequence=[] #只是为了分析而用

    count = 0

    while node:

        i+=1

        count+=1

        if i==k:

            lsa.append(node)

            node_stored_position_sequence.append(count) #只是为了分析而用

            i=0

        last_node=node

        node=node.next

    if i>0:

        lsa.append(last_node)

    # print(node_stored_position_sequence)

    # 如果n=100的话,这里node_stored_position_sequence应该存了 [11, 22, 33, 44, 55, 66, 77, 88, 99]个node.

    # 到这一步为止 time用了2n, space用了K

    # -------第三步: 反向打印------

    # 我们已经存了每第sqrt(n)个node的位置, 那么要如何反过来呢?

    # 每一次我们pop一个node, 并且记录上一次被pop的那个.

    # 处理最后一个node就是:顺序 node = node.next地把结果存起来,存到之前存的那个为止

    # 比如我们存22号node, 就一路 node = node.next 的把结果保存到一个list里, 直到遇到33号为止

    # 存完[22, 23, 24... 32]之后, 我们反着打印. 反着打印花的时间是K.

    # 这样我们操作K次, 每次使用K的空间.

    # 一共space cost是K, time cost则是n+n + K*K = 3n =  O(n).

    start_node=lsa.pop()

    print(start_node.value)

    while lsa: # this happens K times. K = sqrt(K)

        last_printed_node=start_node

        start_node=lsa.pop()

        node=start_node

        ssa=[]

        while node!=last_printed_node:

            ssa.append(node)

            node=node.next

        # [print(v.value, end=" ") for v in ssa]

        # 如果打印的话, 这一步应该打印 sqrt(n) 次, 每一次打印一个 sqrt(n)长度的数组

        ssa.reverse()

        for node in ssa:

            print(node.value)

Q5 : Consider the problem of given an integer n, generating all possible permutations of {1,2,3...n}

• 了解这道题里的复杂度分析是最重要的一点.

举个例子

permute(3) = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

显然 如果已经知道了permute(2), 那permute(3)则只需要在每一个permute(2)的任意一位置加入3这个数字 ,

[[1, 2], [2, 1]]

[[1,2,3], [1,3,2], [3,1,2]

[[2,1,3], [2,3,1], [3,2,1]].

所以, 时间复杂度由T(n) = n * T(n-1) + O(1) , 可以推出时间复杂度是 O(N!)

空间: O(N!) 因为要记录排列组合本身就需要O(N!)这么大的空间

• recursive method(推荐)

def permute(n):

    '''

    :type n: int

    :rtype: List[List[int]]

    return the list contains each lists of permutation

    from {1,2,..n}

    '''

    l = []

    s = []

    v = [0 for i in range(n+1)]

    # 我们不用index 0的位置, 因为题目要求permute从1到n

    # 1 based index

    def dfs(l,s,v,index):

        #start is for the beginning position

        if index==n+1:

            l.append(s[:]) #记录当前组合

            return

        else:

            for i in range(1,n+1):

                if v[i]==0:

                    s.append(i)

                    v[i]=1

                    dfs(l,s,v,index+1)

                    v[i]=0

                    s.pop() #回溯操作

    dfs(l,s,v,1)

    return l

print(permute(3))

• iterative method(Heap's algorithm)

def permute_iterative_heap_s_algorithm(n):

    """

    :type n: int

    :rtype: List[List[int]]

    """

    c = [0 for i in range(n)]

    A = [i+1 for i in range(n)]

    i = 0

    res= [A[:]]

    while i < n:

        if  c[i] < i:

            if i%2==0:

                A[0],A[i] = A[i], A[0]

            else:

                A[c[i]], A[i] = A[i],A[c[i]]

            res.append(A[:])

            c[i] += 1

            i = 0

        else:

            c[i] = 0

            i += 1



    return res