Linked List
单链表和各种操作
Python List,存储是连续的(store all data sequentially in memory). 所以如果想要在list中插入元素,需要为原有的list分配新的空间,把原来的list和想插入的元素放在足够大的新的位置,而不是假设原数组的下一个位置没有元素直接去占领。
如何插入数据但不让原来的数据移动?
Linked List
linkedlist虽然也是线性结构,但它对内存单元的要求没有list这样严格,所以它在内存中的存储可以是不连续的。通过对ref的连接,就可以把元素串在一起。从逻辑上看,它依然是一个线性结构,但是在内存上不要求一个挨着一个。每一个object都有对另一个object的引用,可以很方便找到下一个object在哪里。
链表Linkedlist由节点组成,每个节点包含一个data和一个表示结构的存储(reference),reference存储的是下一个object的地址。如果知道链表中的第一个节点,就可以通过不断访问它的next来遍历它的结构。
OOP——object oriented programming
Python处理的基本单元是对象(object)Anything can be an object.
Object:
States ,每个对象有特有的状态(eg. 特征,属性)。比如汽车的颜色、轮子、品牌、大小、重量、型号、排量... 都描述了汽车的特点。更抽象的,速度是汽车的物理状态。
Behavior, 对象的行为,描述了能对对象做什么事,有什么样的互动。比如汽车,能跑,能加速或减速、前进或后退。
以上就是面向对象最核心的概念。
Class:
无论马自达还是兰博基尼,有唯一的VIN-number.定义class就描述了一个对象应该具有的状态和行为是什么。class是对于对象的描述,一个class是一个blueprint,描述了一系列我们想要的object具备的特点是什么。
Singly Linked List
一个单链表由0个或多个链节点(a list node)组成。从OOD的角度,如何构造一个list node?
构造List Node
States: data + reference
class ListNode(object):
def __init__(self, value): #双下划线,特殊函数 名字是固定的,也是自己写class时最重要的函数。它的功能本质上是Initialize the object that you create
self.next = None #初始化时更make sense的是直接None它 因为只有一个object的时候没有指向 但也可以self.next=next, 在一开始传两个参数
self.value = value
node1 = ListNode("H") #Python和其他的不同,self不是用户自己传的,是python传的,所以用户传的是value。
node2 = ListNode("E")
node1.next = node2
self 是一个满足class ListNode的具体object,所以是对self进行初始化。在初始化时,为了满足对于state的要求,data和ref,就有了self.next 和 self.value. 分别对应reference,data。
当运行到line6时,
第一步:Python Environment创建了一个ListNode这样class的一个object
第二步:Python调用了__init__这个初始化函数。
创建object和写一个class之间是独立的,只有在line6和7运行时才会创建一个object。list node object的value指向一个字符串,而reference什么都不指向。
line9,从物理含义上,让node1里的next存node2的地址。所以node1走到next就能找到node2。这就让两个list node object产生了联系。
对于一个单链表,最基本的操作就是对这个list进行遍历(traverse)。
在这里最容易犯的错误是dereference的时候在None上操作了 比如

这里temp.next=temp.next.next没问题,但是current.next=current.next.next就会报错
Traverse 遍历
遍历一个单链表,将它的值打出来。head是最重要的,head指的是一个单链表中的头节点。如果真要手写,那么我们会写的可能是 从第一个print head.value写到最后一个print head.next.next.next.value
或者,用循环iteration或递归recursion来遍历。
def traverse(head):
while head is not None: #while head 等价
print head.value
head = head.next
注意head是一个reference,并不是一个value。就像是身份证可以代表人,但是身份证和本人是两个完全不同的物理存在。所以line4的含义是reference的箭头。
遍历是其他所有操作的基础,帮助我们从头节点走到最后一个节点。
Search 搜索
search by index
假设第一个list node的index是0,给一个单链表,找对应index的节点,输出。如果找不到,return None。
所以这个问题的核心还是遍历traverse。
一个好的code应该有对于function的specification和一个return value的expectation。所以这些部分应该作为注释先写出来,也不容易忘记这个function是为了什么。
我们很多时候要做的第一件事是先check输入和expectation是否符合,也就是check validity。对于我们的问题来说,可能是空链表(head is None)或者index<0。
def search_by_index(head):
if head is None or index < 0:
return None
接下来,错误的做法是,我们不能直接定义一个jump_times去跳index次,因为很可能就越界了。但是,如果我们跳完之后发现自己已经到了None,就可以直接返回None. 所以我们只需要在原来遍历的基础上加一个条件
for jump_times in xrange(index):
head=head.next
if head is None:
return None
return head
或者用个while loop
while (index>0 and head!= None):
head=head.next
index--
# index<=0 or head==None
return head
search by value
每个链节点都有一个value,所以,给定一个value,看它是否在链表里,如果在,返回它的index,如果不在,返回None。
def search_by_value (head,value):
if not head:
return None
while head is not None:
if head.value==value:
return head
head = head.next
return None
相等关系的判断:
== means equality test
is means identity test
比如 a, b = [1], [1]
print a==b 打印True 内容相同,都是1
print a is b 打印False 这两个是不是指向同一个object
a=[1]
b=a 让b也指向a所指向的object
print a is b 输出的是True
a = None
print a is None 输出是True,因为None是一个有且只有一个的object 所以再定义一个b=None 问print a is b 依然会输出true
a=ListNode(1)
b=ListNode(1)
print a==b 输出是False!!!
这要非常注意,因为在Python中,如果在class中没有做比较关系的定义(__eq__),那么在equality test(也就是==)中,这就完全等于identity test (is)。
class listnode(object):
def __init__(self, value):
self.value=value
self.next=None
def __eq__(self, other):
return isinstance(other, ListNode) and self.value == other.value
其中,__eq__是python中在实现a==b.
isinstance()也是必须的,因为我们需要保证两个被比较的object有相同的类型含义。
比如如果我们定义了另一个listnode object,
class AnotherObject(object):
def __init__(self, value):
self.value = value
a=ListNode(1)
b=AnotherObject(1)
此时就不对了。
Add 插入
Add to index
def add_to_index(head, index, value):
#head: type node, the first node of the passed singly linked list
#index: type int, the position where you want to insert (starting from 0)
#value: type *, the value that will be referred by the newly added list node object if our operation is successful
#return: 必须返回一个头节点(修改后的链表的头节点),不然找不见list,也不知道这个function是否成功了
if index == 0:
new_head = ListNode(value)
new_head.next = head
return new_head
else:
prevNode = search_by_index(head, index-1)
if prevNode is None:
return head
new_node = ListNode(value)
new_node.next = prevNode.next
prevNode.next = new_node
return head
为了add a new node,其实不能直接走到index,而是要走到index-1的位置,因为单链表只能往后走,不能往前走。但是很棘手的是,头节点没有index-1. 所以定义一个new_head,这也是如果我们改动了头节点然后返回的。
注意15~17行的顺序: 先让new_node指向真正的下一个,再让prev指向new_node。如果把16和17调换,那就不对了,因为new_node就变成了指向自己,后面的没了。有了环形结构,这就不是单链表了。
def add_to_index(head, index, val):
fake_head = ListNode("whatever you want")
fake_head.next = head
insert_place = searchbyindex(fake_head, index)
if insert_place is None: #在一个不存在的index或者越界的位置插入新的node
return fake_head.next #此时返回的依然是原来的linkedlist
new_node = ListNode(val)
new_node.next = insert_place.next
insert_place.next = new_node
return fake_head.next
注意的是,加了sentinel(fake_head)之后,如果想在原来的index之前插入一个元素,在加入了fake head后,就等价于在以fake head为首的新链表的index之后做插入。
在return时return的都是fake_head.next. 因为引入fake_head的原因是避免对head单独讨论。但是!fake_head并不是真正的头节点,所以真的头节点永远都是fake_head后面的1个。
如果是在原来链表的头节点插入,那么fake_head之后的就是新的头节点。
dummy node 在两种情况非常好用1)在构建一个新的链表不知道谁是头的时候(比如谁小移谁,合并了两个linkedlist)2)在需要对头进行操作的时候(增删改)
Remove 删除
Remove from index
def remove_from_index (head, index):
# validity check is implicit, in search_by_index function
# find the node with a reference of index
# return the fake_head
fake_head = ListNode(None)
fake_head.next = head
prev_node = search_by_index(fake_head, index)
if prev_node is None or prev_node.next is None:
# it is likely that we find the prev of the node, but not the node itself
return fake_head.next
remove_node = prev_node.next
prev_node.next = remove_node.next
remove_node.next = None #or don't write anything
return fake_head.next
class ListNode(object):
def __init__(self, value):
self.value=value
self.next=None
class SinglyLinkedList(object):
def traverse(self, head):
while head:
print (head.value)
head=head.next
def searchByIndex(self, head, index):
#sanity check
if index<0 or not head:
return None
for jump_steps in range(index):
head=head.next
if head is None:
return None
return head
def searchByValue(self, head, value):
if not head:
return None
while head is not None:
if head.value==value:
return head
head=head.next
return None
def addByIndex(self, head, index, value):
newnode=ListNode(value)
fakehead=ListNode(None)
fakehead.next=head
insertplace=self.searchByIndex(fakehead, index)
if insertplace is not None:
newnode.next=insertplace.next
insertplace.next=newnode
return fakehead.next
def deleteNode(self, head, index):
fakehead=ListNode(None)
fakehead.next=head
pred_node=self.searchByIndex(fakehead, index)
if pred_node is not None and pred_node.next is not None:
pred_node.next=pred_node.next.next
pred_node.next.next = None
return fakehead.next
class Solution(object):
def numberOfNodes(self, head):
"""
input: ListNode head
return: int
"""
# write your solution here
steps = 0
while head:
steps+=1
head=head.next
return steps
How to design a linked list class
class _ListNode(object):
def __init__(self, val):
self.value = val
self.next = None
class MyLinkedList(object):
def __init__(self):
#一般不是从状态开始想起,而是想,它能实现什么样的功能,再在class中实现这些功能 这叫实现 是实现的一部分 我们一般不希望用户看到实现的一部分,而只是希望用户看到接口是什么
# we should have a reference that ALWAYS points to the first node of the internally maintained singly linked list
self._head = None #逻辑上的实现,这里None说得过去(区分下面的)永远maitain一个指向单链表的头节点
self._tail = None #永远指向单链表最后一个元素
self._size = 0 #永远表示 # of nodes in the list
def _get(self,index):
# return the node we found, 区分于下面的这个
# assume index is valid.
node = self._head #不然就会破坏上面的ALWAYS
for _ in xrange(index):
node = node.next
return node
def get(self, index): #instance method or object method 调用这些方法一定要通过对象来调用 free function就不用self(写在class外面的不用)
#返回第index个node的node value
# How do we know the index is out of range?
if index < 0 or index >=self._size:
return -1
return self._get(index).value
def addAtHead(self, index, val):
#如果一个链表只有一个节点,它既是头节点,又是尾节点
if size._size ==0:
self._head = self._tail =_ListNode(val)
self._size += 1
else:
new_head = _ListNode(val)
new_head.next = self._head #新的头节点的后面应该是原来的头节点
self._head = new_head
self._size += 1
def addAtTail(self, val):
# 需要先判断现在的链表是不是空的,不然默认tail是None 就没办法.next了
if size._size ==0:
self._head = self._tail =_ListNode(val)
self._size += 1
else:
self._tail.next = _ListNode(val)
self._tail = self._tail.next
self._size += 1
def addAtIndex(self, index, val):
def deleteAtIndex(self, index):
if index < 0 or index>= self._size:
return
if index==0:
self._head = self._head.next
self._size -= 1
# 如果remove掉的就是原来链表的最后一个
if self._size == 0:
self.tail = None
else:
node = self._get(index-1)
node.next=node.next.next
# 如果remove掉的就是原来链表的tail
if index=self._size -1:
self._tail=node
self._size -=1
ll = MyLinkedList() # We should have an empty linked list after initialization (not None) 容积在,只是容器是空的
ll = MyLinkedList() 这个clause结束后调用init 初始化函数,创建object
ll.addAtHead(1) 等价于MyLinkedList.addAtHead(ll, 3)
关于前面的_ 在Python中,如果一个entity(variable or function)是我们自己实现的一部分,那应该自己来命名自己的entity,比如_get。用户不应该直接去改变这个。另外,前面maintain了几个状态,我们在做interface的时候也需要去考虑每个状态
双链表
总结对比 Linked List vs. List

什么时候用list?
想要O(1)获取value
什么时候linkedlist
想要O(1)remove,delete,add
题
Insert in a Sorted Linkedlist
Assumption - 是不是一定有比target大的数 : 不知道 - Duplication 的时候还要不要加 : 可以有 插一个一样的在它之前 - Data Type 万一是字符串、double...: 都是整数 - Sorted是ascending还是descending 比如没有给例子 : ascending
Data Structure: - dummyHead 因为新头旧头可能不是一个头 - curr 判断target是否是要插在curr的后面 也就是和curr.next比较
Initialize - curr=dummyHead - targetNode= new ListNode(target)
For each step: case 1: 先保证 case 2:
Termination Condition: curr.next==null
class Solution(object):
def insert(self, head, value):
"""
input: ListNode head, int value
return: ListNode
"""
# write your solution here
dummyHead=ListNode('dummy')
dummyHead.next = head
prev=dummyHead
while prev.next and prev.next.val < value:
prev=prev.next
newnode = ListNode(value)
newnode.next = prev.next
prev.next = newnode
return dummyHead.next
在Java中,logical operator有short circuit 而&&和||是这种逻辑运算符;相反,&和|是bitwise operation,没有short circuit。在Python中,and和or是logical operation。位运算是为了数本身,是数学上的操作。
在或操作上前一个是false或者且操作上前一个是true才会短路。
Reverse a Singly Linked List
如果iterative way
面试过程clarification, algorithm, result, test的顺序一步步来;
One sentence high-level description of the problem Do a linear scan on each element, move next pointer to the previous element
Clarification of the problem assumptions
Data Structure (物理意义 or semantic) 不变的关系 curr: the node which I want to change its next to its previous node prev: curr's previous node in the input linkedlist next: curr's next node in the input linkedlist
Algorithm - initialize prev: null, curr=head, next=curr.next - for each step: curr.next=prev, 先移previous,prev=curr 再移curr,curr=next (这一步也可以放在第一步)最后移next,next=curr.next - termination condition: curr是要被反转的,所以一定是 curr==null 时间O(n) 空间O(1)
class Solution(object):
def reverse(self, head):
"""
input: ListNode head
return: ListNode
"""
# write your solution here
prev, curr = None, head
while curr:
next=curr.next ##preserve the next pointer since we are changing it afterwards
curr.next=prev
prev=curr
curr=next
return prev
如果recursively
翻转后面的那些
让后面的node2指向自己 node2.next=head
让head.next=null
新的linkedlist的头 也就是node n
时间、时间都是O(n)
def reverse (head): #reverse the linkedlist headed by head
if head is None or head.next is None:
# linked list is empty or contains only one node
return head
node = reverse(head.next)
# 当前head的头节点就是所反转list的尾节点 在执行完head.next这一行之后,head.next的值还是原来的
tail = head.next
tal.next = head
head.next = None
return node
class Solution(object):
def reverse(self, head):
"""
input: ListNode head
return: ListNode
"""
# write your solution here
if not head or not head.next:
return head
newhead = self.reverse(head.next)
head.next.next=head
head.next=None
return newhead
Reverse Linked List in Pairs
Reverse pairs of elements in a singly-linked list.
Examples
L = null, after reverse is null
L = 1 -> null, after reverse is 1 -> null
L = 1 -> 2 -> null, after reverse is 2 -> 1 -> null
L = 1 -> 2 -> 3 -> null, after reverse is 2 -> 1 -> 3 -> null
class Solution(object):
def reverseInPairs(self, head):
"""
input: ListNode head
return: ListNode
"""
# write your solution here
if not head or not head.next:
return head
node1, node2 = head, head.next
rest=self.reverseInPairs(node2.next)
node1.next=rest
node2.next=node1
return node2
Remove all vowels in a linked list
curr:物理意义是什么? 不是让curr和target比较,而是curr.next和target作比较,这样就不需要再来一个prev了
Termination Condition
class Solution(object):
def removeElements(self, head, val):
"""
input: ListNode head, int val
return: ListNode
"""
# write your solution here
dummyHead = ListNode('dummy')
dummyHead.next = head
prevNode = dummyHead
while prevNode.next:
if prevNode.next.val==val:
prevNode.next=prevNode.next.next #注意这里不要移动prevNode!
else:
prevNode=prevNode.next
return dummyHead.next
def remove(head):
fake_head = ListNode(None)
fake_head.next = head
prev = fake_head
curr = head
vowel = set(['a', 'e', 'i', 'o', 'u'])
while curr:
if curr.val in vowel:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return fake_head.next
Remove Nth Node From End of List
设立两个指针p1和p2,一开始它们都指向队首的dummy,然后单独令p2向后跳n个元素,这样p1和p2之间就相隔了n个元素,如果这个时候p2发现自己不能完整跳完n步,说明给的数字太大了,越界,所以直接return。 令p1和p2同时向后不断跳,直到p2已经到了最后一个node,由于此时p1和p2之间相隔n个元素,所以p1的下一个元素就是我们要删除的元素了。
为了方便删除第一个元素,建议设立一个空的“头结点”。
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
input: ListNode head, int n
return: ListNode
"""
# write your solution here
dummyHead=ListNode('dummy')
dummyHead.next=head
curr,fast=dummyHead,dummyHead
while n>0 and fast:
fast=fast.next
n-=1
if not fast:
return dummyHead.next
while fast and fast.next:
fast=fast.next
curr=curr.next
curr.next=curr.next.next
return dummyHead.next
Partition a Linked List
Given a linked list and a target value T, partition it such that all nodes less than T are listed before the nodes larger than or equal to target value T. The original relative order of the nodes in each of the two partitions should be preserved.
Examples
L = 2 -> 4 -> 3 -> 5 -> 1 -> null, T = 3, is partitioned to 2 -> 1 -> 4 -> 3 -> 5 -> null
Assumption: - < 和 >= - Duplication - Integer
Data Structure - dummyHeadSmall smallTail - dummyHeadLarge LargeTail
最后一定记得把largetail的尾巴断了
class Solution(object):
def partition(self, head, target):
"""
input: ListNode head, int target
return: ListNode
"""
# write your solution here
dummyHeads=ListNode('Small')
tails = dummyHeads
dummyHeadl=ListNode('Large')
taill = dummyHeadl
curr=head
while head:
if head.val<target:
tails.next=head
tails=tails.next
else:
taill.next=head
taill=taill.next
head = head.next
tails.next=dummyHeadl.next
taill.next=None #最后一定记得把largetail的尾巴断了 不然就是一个loop了
return dummyHeads.next
Add two linked list which represents large number
大数:传统语言int long的范围是 范围之外称为大数
在Python里自动支持大数,转化好了
如何靠右对齐,个位对齐? Reverse
进位 carry
两个linkedlist不等长 所以注意while循环的break,post-processing
reverse最后的结果
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
input: ListNode l1, ListNode l2
return: ListNode
"""
# write your solution here
dummyHead = ListNode('dummy')
tail=dummyHead
curr = 0
while l1 or l2 or curr!=0:
if l1:
curr += l1.val
l1=l1.next
if l2:
curr += l2.val
l2=l2.next
tail.next=ListNode(curr%10)
tail=tail.next
curr = curr//10
return dummyHead.next
def reverse_list(node):
previous_node = None
while node:
next_node = node.next
node.next = previous_node
previous_node = node
node = next_node
return previoous_node
def add_list(head1, head2):
#1 reverse
new_head1 = reverse_list(head1)
new_head2 = reverse_list(head2)
#2 add
fake_head = ListNode(None)
cur_node = fake_head
carry = 0
while new_head1 and new_head2:
temp_sum = new_head.val + new_head2.val + carry
carry = temp_sum/10
cur_node.next = ListNode(temp_sum%10)
cur_node = cur_node.next
new_head1 = new_head1.next
new_head2 = new_head2.next
#3 post processing
while new_head1:
temp_sum = new_head1.value+carry
carry = temp_sum/10
cur_node.next = ListNode(temp_sum%10)
cur_node = cur_node.next
new_head1 = new_head1.next
while new_head2:
temp_sum = new_head2.value+carry
carry = temp_sum/10
cur_node.next = ListNode(temp_sum%10)
cur_node = cur_node.next
new_head2 = new_head2.next
if carry>0:
cur_node.next = ListNode(carry)
return reverse_list(fake_head.next)
If a linked list is a palindrome
方法一:Copy Linked List and Reverse
make a copy
reverse the copied list
compare the two
缺点是空间消耗是O(n)
方法二:从中点reverse
find the middle of the list
cut in the middle and reverse the second half
compare first half and reversed second half
关于快慢指针找中点
class Solution(object):
def middleNode(self, head):
"""
input: ListNode head
return: ListNode
"""
# write your solution here
if not head or not head.next:
return head
slow,fast=head,head
while fast.next and fast.next.next:
slow=slow.next
fast=fast.next.next
return slow
注意while的条件,这其实是提前一点停止,保证slow在中间而不是中间右一个
def is_palindrome(head):
fake_head = ListNode('fake_head')
fake_head.next = head
mid_node = find_mid(head)
head2 = mid_node.next
#break
mid_node.next = None
head1 = head
head2 = reverse_list(head2)
while head1 and head2:
if head1.value != head2.value:
return False
head1 = head1.next
head2 = head2.next
return True
#test
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(0)
corner case:None、数量不同、奇偶
class Solution(object):
def isPalindrome(self, head):
"""
input: ListNode head
return: boolean
"""
# write your solution here
if not head or not head.next:
return True
mid = self.findmin(head)
head1, head2 = head, mid.next
mid.next = None
head2 = self.reverse(head2)
return self.compare(head1, head2)
def findmin(self, head):
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverse(self, head):
if not head or not head.next:
return head
newhead = self.reverse(head.next)
head.next.next=head
head.next=None
return newhead
def compare(self, head1, head2):
while head1 and head2:
if head1.val!=head2.val:
return False
head1=head1.next
head2=head2.next
return True
找中点
clarrification: 一上来要问clarification: 比如,偶数个的node的时候中点是左边的还是右边的? 左边的,因为有左可以找到右,有右就找不到左了;以及左边的会更方便做题的分析,比如merge sort
data structure: slow and fast, fast之前包含fast的节点个数=2*slow之前包含slow的节点个数
initialization:slow=head, fast=head.next
class Solution(object):
def middleNode(self, head):
"""
input: ListNode head
return: ListNode
"""
# write your solution here
# # of node on the left of fast = 2* # of node on the left of slow (including)
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
slow=slow.next
fast=fast.next.next
return slow
online vs. offline:
offline algorithm: 必须读出所有的数据 online algorithm: 不需要读出所有数据
如果有一个linkedlist,不知道linkedlist有多长,那么可以先读完一遍然后再读半遍; 如果是slow&fast,物理意义永远不变,哪怕只做了一半断电了,这个时候slow停下的位置依然是中点;这对于“数据量大小未知”的问题非常方便。
Merge 2 linked list
Clarification - ascending or descending - data type: integer - what to do when there is duplication:
Data Structure: DummyHead curr1 curr2 curr
class Solution(object):
def merge(self, one, two):
"""
input: ListNode one, ListNode two
return: ListNode
"""
# write your solution here
dummyHead=ListNode('dummy')
tail = dummyHead
curr1, curr2 = one, two
while curr1 and curr2:
if curr1.val<=curr2.val:
tail.next=curr1
curr1=curr1.next
else:
tail.next=curr2
curr2=curr2.next
tail = tail.next
tail.next = curr1 if curr1 else curr2
return dummyHead.next
ReOrder Linked List
Reorder the given singly-linked list N1 -> N2 -> N3 -> N4 -> … -> Nn -> null to be N1- > Nn -> N2 -> Nn-1 -> N3 -> Nn-2 -> … -> null
Examples
L = null, is reordered to null
L = 1 -> null, is reordered to 1 -> null
L = 1 -> 2 -> 3 -> 4 -> null, is reordered to 1 -> 4 -> 2 -> 3 -> null
L = 1 -> 2 -> 3 -> null, is reordred to 1 -> 3 -> 2 -> null
class Solution(object):
def reorder(self, head):
"""
input: ListNode head
return: ListNode
"""
# write your solution here
if not head or not head.next:
return head
mid = self.findmid(head)
head1 = head
head2 = mid.next
mid.next = None
head2 = self.reverse(head2)
newhead = self.merge(head1, head2)
return newhead
def findmid(self, head):
slow, fast = head, head.next
while fast and fast.next:
slow=slow.next
fast=fast.next.next
return slow
def reverse(self, head):
if not head or not head.next:
return head
newhead = self.reverse(head.next)
head.next.next=head
head.next=None
return newhead
def merge(self, head1, head2):
dummyHead=ListNode('dummy')
tail=dummyHead
while head1 and head2:
tail.next=head1
head1=head1.next #注意这一行和下一行不能换位置 要先让h1脱险
tail.next.next=head2
head2=head2.next
tail=tail.next.next
tail.next = head1 if head1 else head2
return dummyHead.next
Merge Sort Linked List
class Solution(object):
def mergeSort(self, head):
"""
input: ListNode head
return: ListNode
"""
# write your solution here
if not head or not head.next:
return head
mid = self.findmid(head)
head1, head2 = head, mid.next
mid.next = None
left = self.mergeSort(head1)
right = self.mergeSort(head2)
return self.merge(left, right)
def findmid(self, head):
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
slow=slow.next
fast=fast.next.next
return slow
def merge(self, head1, head2):
dummyHead = ListNode('dummy')
tail = dummyHead
while head1 and head2:
if head1.val<head2.val:
tail.next=head1
head1=head1.next
else:
tail.next=head2
head2=head2.next
tail=tail.next
tail.next=head1 if head1 else head2
return dummyHead.next
链表、环的问题
Check if linkedlist has cycle
class Solution(object):
def checkCycle(self, head):
"""
input: ListNode head
return: boolean
"""
# write your solution here
# if not head:
# return False
slow, fast = head, head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
if fast==slow:
return True
return False
Cycle Node In Linked List
找到环的入口点?
定理:slow和fast相遇点为p,让slow从head开始,fast从p开始,每次往后各走一步,直到slow和fast再次相遇,则相遇点即为环的入口。
证明:
当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(n>=1)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:
2s = s + nr 即:s= nr
设整个链表长L,环入口与相遇点距离为x,起点到环入口点的距离为a。
则s=a+x, L=a+r。那么a + x = nr = (n – 1)r +r = (n-1)r + L - a,则有a = (n-1)r + (L – a – x)。
(L–a–x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。
class Solution(object):
def findCycle(self, head):
"""
input: ListNode head
return: ListNode
"""
# write your solution here
if not head or not head.next:
return None
slow, fast=head, head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
if slow==fast:
break
if slow==fast:
slow=head
while slow!=fast:
slow=slow.next
fast=fast.next
return slow
return None
如何知道环的长度?
记录下碰撞点meet,slow、fast从该点开始,再次碰撞所走过的操作数就是环的长度r
Insert into a Cyclic Sorted List
class Solution(object):
def insertCircularList(self, head, newVal):
"""
input: ListNode head, int newVal
return: ListNode
"""
# write your solution here
newNode=ListNode(newVal)
if not head:
newNode.next=newNode
return newNode
prev, curr = head, head.next
while True:
if prev.val<=newVal and curr.val>=newVal: #新节点需要插入到某2个节点之间,这两个节点是顺序的
break
if prev.val>curr.val and (curr.val>newVal or prev.val<newVal): #新节点需要插入到某2个节点之间,这两个节点是有break的 5——>6——>1 插入0 或者插入7
break
if curr is head: #遍历链表找到尾结点
break
prev = prev.next
curr = curr.next
newNode.next=curr
prev.next=newNode
return head
判断两个无环单链表是否相交
如果相交,给出相交的第一个点。
一、将其中一个链表L2首尾相连,检测另外一个链表L1是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。但是这样改变了输入的结构,不太好。
二、如果两个链表有一个公共结点,那么该公共结点之后的所有结点都是重合的。那么,它们的最后一个结点必然是重合的。因此,我们判断两个链表是不是有重合的部分,只要分别遍历两个链表到最后一个结点。如果两个尾结点是一样的,说明它们用重合;否则两个链表没有公共的结点。
在上面的思路中,顺序遍历两个链表到尾结点的时候,我们不能保证在两个链表上同时到达尾结点。这是因为两个链表不一定长度一样。但如果假设一个链表比另一个长l个结点,我们先在长的链表上遍历l个结点,之后再同步遍历,这个时候我们就能保证同时到达最后一个结点了。由于两个链表从第一个公共结点开始到链表的尾结点,这一部分是重合的。因此,它们肯定也是同时到达第一公共结点的。于是在遍历中,第一个相同的结点就是第一个公共的结点。
在这个思路中,我们先要分别遍历两个链表得到它们的长度,并求出两个长度之差。在长的链表上先遍历若干次之后,再同步遍历两个链表,知道找到相同的结点,或者一直到链表结束。此时,如果第一个链表的长度为m,第二个链表的长度为n,该方法的时间复杂度为O(m+n)。
判断两有环单链表是否相交
思路:
先判断两链表是否均有环,有一个无环则不相交
若入环节点一样,则相交
若入环节点不一样,则从一个入环点往后遍历,若能和另一个链表的入环点相遇则相交,若遍历回自己的入环点还没相遇,则不相交
注意:
第 3 步里从一个入环点往后遍历,注意起始条件
Last updated