- Merge k Sorted Lists 解：use dummy node, PriorityQueue, put(node.val, node) in q.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
from Queue import PriorityQueue
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
dummy = ListNode(None)
curr = dummy
q = PriorityQueue()
for node in lists:
if node:
q.put((node.val, node))
while q.qsize() > 0:
curr.next = q.get()[1]
curr = curr.next
if curr.next:
q.put((curr.next.val, curr.next))
return dummy.next
Add Two Numbers
Populating Next Right Pointers in Each Node
" if(root.right!=null&&root.next!=null){
root.right.next=root.next.left;
}"
Merge Two Sorted Lists
"dummy = ListNode(0)
tmp = dummy
while l1 and l2:
if l1.val < l2.val:
tmp.next = l1
l1 = l1.next
else:
tmp.next = l2
l2 = l2.next
tmp = tmp.next
if l1:
tmp.next = l1
else:
tmp.next = l2
return dummy.next"
Reverse Linked List
"class Solution:
def reverse(self, head):
curt = None
while head != None:
temp = head.next
head.next = curt
curt = head
head = temp
return curt"
Copy List with Random Pointer
"class Solution(object):
def copyRandomList(self, head):
""""""
:type head: RandomListNode
:rtype: RandomListNode
""""""
if head == None:
return None
mymap = {}
nHead = RandomListNode(head.label)
mymap[head] = nHead
p = head
q = nHead
while p!= None:
q.random = p.random
if p.next != None:
q.next = RandomListNode(p.next.label)
mymap[p.next] = q.next
else:
q.next = None
p = p.next
q = q.next
p = nHead
while p!= None:
if p.random != None:
p.random = mymap[p.random]
p = p.next
return nHead"
Insert into a Cyclic Sorted List
"class Solution:
# @param {ListNode} node a list node in the list
# @param {int} x an integer
# @return {ListNode} the inserted new list node
def insert(self, node, x):
# Write your code here
if node is None:
node = ListNode(x)
node.next = node
return node
p = node
prev = None
while True:
prev = p
p = p.next
if x <= p.val and x >= prev.val:
break
if (prev.val > p.val) and (x < p.val or x > prev.val):
break
if p is node:
break
newNode = ListNode(x)
newNode.next = p
prev.next = newNode
return newNode"
Delete Node in a Linked List
"def deleteNode(self, node):
""""""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
""""""
node.val = node.next.val
node.next = node.next.next"
- Copy List with Random Pointer
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if head is None:
return None
tmp = head
while tmp:
newnode = RandomListNode(tmp.label)
newnode.next = tmp.next
tmp.next = newnode
tmp = tmp.next.next
tmp = head
while tmp:
if tmp.random:
tmp.next.random = tmp.random.next
tmp = tmp.next.next
newhead = head.next
pold = head
pnew = newhead
while pnew.next:
pold.next = pnew.next
pold = pold.next
pnew.next = pold.next
pnew = pnew.next
pnew.next = None
pold.next = None
return newhead
- Palindrome Linked List
```
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
node = None
while slow:
tmp = slow.next
slow.next = node
node = slow
slow = tmp
while node:
if node.val != head.val:
return False
node = node.next
head = head.next
return True
Linked List Cycle
sol: fast slow
class Solution: """ @param head: The first node of the linked list. @return: True if it has a cycle, or false """ def hasCycle(self, head):
# write your code here
if not head or not head.next:
return False
fast = slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Sort List
sol: merge sort
/**
- Definition for ListNode.
- public class ListNode {
- int val;
- ListNode next;
- ListNode(int val) {
- this.val = val;
- this.next = null;
- }
} / public class Solution { /*
- @param head: The head of linked list.
@return: You should return the head of the sorted linked list,
using constant space complexity.*/ public ListNode sortList(ListNode head) {
// write your code here return mergeSort(head); }public ListNode mergeSort(ListNode head) { if (head == null || head.next == null) {
return head;}
ListNode slow = head; ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next; fast = fast.next.next;} ListNode mid = slow.next; slow.next = null;
ListNode left = mergeSort(head); ListNode right = mergeSort(mid);
return merge(left, right); }
public ListNode merge(ListNode left, ListNode right) { ListNode dummy = new ListNode(0); ListNode cur = dummy;
while (left != null && right != null) {
if (left.val < right.val) { cur.next = left; left = left.next; } else { cur.next = right; right = right.next; } cur = cur.next;}
while (left != null) {
cur.next = left; left = left.next; cur = cur.next;}
while (right != null) {
cur.next = right; right = right.next; cur = cur.next;}
return dummy.next; } }
Median of two Sorted Arrays
sol:
def findMedianSortedArrays(self, A, B):
# write your code here
A = A + B
A.sort()
if len(A) % 2 == 0:
return (A[len(A)/2] + A[len(A)/2 -1]) / 2.0
else:
return (A[len(A)/2])
First Missing Positive
for i in xrange(len(nums)):
while nums[i] > 0 and nums[i] <= len(nums) and nums[nums[i]-1] != nums[i]:
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
for i in xrange(len(nums)):
if nums[i] != i + 1:
return i + 1
return len(nums)+1
```