def traverse(head):
while head is not None: #while head 等价
print head.value
head = head.next
def print_all_nodes(head):
if not head:
return
print head.val
print_all_nodes(head.next)
# or alternatively
if head:
print(head.val)
print(print_all_nodes(head.next))
return
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，这也是如果我们改动了头节点然后返回的。
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
Count number of nodes
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) 容积在，只是容器是空的
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
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
public class Solution {
public ListNode reverse(ListNode head) {
// Write your solution here
ListNode prev = null;
while (head!=null) {
ListNode next=head.next;
head.next=prev;
prev=head;
head=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
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
def remove(head):
fake_head = ListNode(None)
fake_head.next = head
curr = fake_head
vowel = set(['a', 'e', 'i', 'o', 'u'])
while curr and curr.next: #判断是否为None
if curr.next.val in vowel:
curr.next = curr.next.next
else:
curr = curr.next
return fake_head.next
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的范围是 232 范围之外称为大数
在Python里自动支持大数，转化好了
如何靠右对齐，个位对齐？ Reverse
进位 carry
两个linkedlist不等长 所以注意while循环的break，post-processing
reverse最后的结果
这个题目是已经reverse过了的 所以不需要reverse function
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
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
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
Clarification
- ascending or descending
- data type: integer
- what to do when there is duplication:
Data Structure:
DummyHead
curr1
curr2
curr
dummyHead:
(1) When we need to change the head / when the headNode might be changed
(2) When we need to build a new Linked List from scratch (from 0 node)
dummyTail:
When we need to expand elements from the end of the Linked List.
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
Step 1: Find Mid and Split to 2 Linked List
Step 2: Reverse the second Linked List
Step 3: Merge the two Linked List
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
这里可以不需要一开始的sanity check
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
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
