LC Link List

两种通用方法:

list找中点可用一个slow一个fast来做

对于list开始时的特殊情况,可以先建立一个没用的Node,然后当一切处理完之后返回Node.next即可,如此不用考虑特殊情况了。

 

234. Palindrome Linked List

一个slow一个fast,slow每次进1的同时将list反过来,fast则每次进二。当fast没有next next的时候,slow和slow+1(有fast next则是slow+2)分别为反向前半段和后半段的起点。此时只需检查两个list相同即可。

 

160. Intersection of Two Linked Lists

 一个跑完list1跑list2,一个跑完list2跑list1,此时二者所跑过的总距离相同,因此第一个重合的Node为intersection node。

 

148.Sort List

各种Sort的复杂度:https://en.wikipedia.org/wiki/Sorting_algorithm 最快的是d&c,占地最小是bubble

 

138. Copy List with Random Pointer

有两种解决方案,一种在复制list的同时以hash table的形式将list再存一遍,使得可以通过original.random 找到new.random 的node,从而使得deep copy变为可能。第二种是复制的时候不把新list拆出来,而是变成old->copy->old 这种链接方式,使得old.random.next就是copy.random该指的copy的node,最后只需将整个list按奇偶分开即可。

 

109. Convert Sorted List to Binary Search Tree

平衡二叉树可以通过递归来弄,找到中点后将左右分别再构造平衡二叉树即可。

 

142. Linked List Cycle II

如何寻找环开始的node:https://discuss.leetcode.com/topic/17521/share-my-python-solution-with-detailed-explanation

简单来讲,通过快慢node可以确定有没有环,且此时slow走了Head+D,fast走了2Head+2D,而二者的差为n*Loop。于是可知Head = n*Loop – D,由于在确定有环的时候慢速走了D,此时只需要一个node从开始处走,一个node从D处走,其相遇点必为环开始的点。

发表评论

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