Skip to content

Instantly share code, notes, and snippets.

@dapangmao

dapangmao/Linkedlist.md

Last active June 15, 2021 17:56
Show Gist options
  • Save dapangmao/c1f6b7d438c036959a87 to your computer and use it in GitHub Desktop.
Save dapangmao/c1f6b7d438c036959a87 to your computer and use it in GitHub Desktop.
Download ZIP
Linked List
Raw
Linkedlist.md
  • Transform list to linked list
class ListNode:
    def __init__(self, val=None):
        self.val = val
        self.next = None
        self.size = 0
        if val:
            self.size = 1
    def add_to_last(self, x):
        self.size += 1
        if self.val is None:
            self.val = x
        else:
            end = ListNode(x)
            while self.next:
                self = self.next
            self.next = end
    def add_many(self, a):
        for x in a:
            self.add_to_last(x)
    def show(self):
        print self.val
        if self.next:
            self.next.show()
  • Most basic question: reverse singly linked list
# Solution of iteration
def rvs_iter(head):
    prev, current = None, head # Two pointers: previous and current
    while current:
        post = current.next  
        current.next = prev 
        prev = current 
        current = post
    return prev


# Solution of recursion
def rvs_rcs(head):
    if None in [head, head.next]:
        return head
    current = rvs_rcs(head.next)
    head.next.next = head
    head.next = None
    return current
24	Swap Nodes in Pairs	32.5%	Medium
148	Sort List	21.0%	Medium
61	Rotate List	21.9%	Medium
25	Reverse Nodes in k-Group	25.2%	Hard
92	Reverse Linked List II	26.2%	Medium
143	Reorder List	20.6%	Medium
19	Remove Nth Node From End of List	28.6%	Easy
83	Remove Duplicates from Sorted List	34.4%	Easy
82	Remove Duplicates from Sorted List II	24.9%	Medium
86	Partition List	27.2%	Medium
21	Merge Two Sorted Lists	33.2%	Easy
23	Merge k Sorted Lists	21.1%	Hard
141	Linked List Cycle	36.1%	Medium
142	Linked List Cycle II	31.0%	Medium
160	Intersection of Two Linked Lists	27.0%	Easy
147	Insertion Sort List	25.7%	Medium
138	Copy List with Random Pointer	23.9%	Hard
109	Convert Sorted List to Binary Search Tree	27.5%	Medium
2	Add Two Numbers	22.8%	Medium
Raw
questions.py
# Swap Nodes in Pairs
"""
链长为零和1时，直接返回。
先把链表挂到dummy上。分配两个指针，一个prev给dummy，另一个current给head。
两个需要交换的node始终有指针，不会丢链。
用两个条件current and current.next保护循环，兼顾奇数链和偶数链的情况. 用一个暂时变量postpost保护需要交换的node.
prev和current逐步前进.
最后去掉dummy的头，返回。
"""
class Solution:
# @param a ListNode
# @return a ListNode
def swapPairs(self, head):
if not head or not head.next:
return head
prev = dummy = ListNode(-1)
dummy.next = head
current = head
while current and current.next:
postpost = current.next.next
current.next.next = current
prev.next = current.next
current.next = postpost
prev = prev.next.next
current = current.next
return dummy.next
#-------------------------------------------------------------------------------
# Name: Remove Duplicates from Sorted List
# Purpose:
#
# Given a sorted linked list, delete all duplicates
# such that each element appear only once.
# For example,
# Given 1->1->2, return 1->2.
# Given 1->1->2->3->3, return 1->2->3
#-------------------------------------------------------------------------------
def deleteDuplicates(head):
if head is None:
return None
current = head
while current.next:
post = current.next
if current.val == post.val:
current.next = current.next.next # Move two steps ahead
else:
current = post # Move one step
return head
a = [1, 1, 2, 3, 3]
head = ListNode()
head.add_many(a)
b = deleteDuplicates(head)
b.show()
#-------------------------------------------------------------------------------
# Name: Remove duplicate in unsorted linked list
# Purpose:
#
#-------------------------------------------------------------------------------
def removeDep(head):
if head is None:
return
current, prev = head, None
saved = set()
while current:
if current.val in saved:
prev.next = current.next
else:
saved.add(current.val)
prev = current
current = current.next
return head
a = [6, 1, 2, 3, 4, 5, 2, 5, 3, 2, 2, 6, 6, 6, 6]
head = ListNode()
head.add_many(a)
b = removeDep(head)
b.show()
```
- Reverse linked list
```python
#-------------------------------------------------------------------------------
# Name: Linked List Cycle II
# Purpose:
#
# Given a linked list, return the node where the cycle begins.
# If there is no cycle, return null.
#-------------------------------------------------------------------------------
def reverseBetween( head, m, n):
dummy = ListNode(0)
dummy.next = head
prev = dummy
i = 1
while prev and i < m:
prev = prev.next
i += 1
mNode = prev.next
current = mNode.next
while current and i < n:
right = current.next
current.next = prev.next
prev.next = current
mNode.next = right
current = right
i += 1
return dummy.next
a = [i for i in range(1, 6)]
head = ListNode()
head.add_many(a)
b = reverseBetween(head, 2, 4)
b.show()
#-------------------------------------------------------------------------------
# Name: Partition List
# Purpose:
#
# Given a linked list and a value x, partition it such that all
# nodes less than x come before nodes greater than or equal to x.
# You should preserve the original relative order of the nodes
# in each of the two partitions.
# For example,
# Given 1->4->3->2->5->2 and x = 3,
# return 1->2->2->4->3->5.
#-------------------------------------------------------------------------------
def partition(head, x):
smaller_pntr = smaller = ListNode(0) # Setup pointers and copies
larger_pntr = larger = ListNode(0)
while head:
if head.val < x:
smaller.next = head
smaller = smaller.next
else:
larger.next = head
larger = larger.next
head = head.next
smaller.next = larger_pntr.next
larger.next = None
return smaller_pntr.next
a = [1, 4, 3, 2, 5, 2]
head = ListNode()
head.add_many(a)
b = partition(head, 3)
b.show()
#-------------------------------------------------------------------------------
# Name: Remove Nth Node From End of List
# Purpose:
#
# Given a linked list, remove the nth node
# from the end of list and return its head.
# For example,
# Given linked list: 1->2->3->4->5, and n = 2.
#
# After removing the second node from the end,
# the linked list becomes 1->2->3->5.
#
# Note:
# Given n will always be valid.
# Try to do this in one pass.
#
# 这道题目思路很简单，主要是定位从后往前数第n个元素，然后把他的前一个的next赋值为他的next即可。
# 注意第一个for循环后 fast-slow=n. 然后两者一起前进直到fast是最后一个元素
# 此时slow是倒数第n+1个元素 (fast-slow=n) 也就是要删除元素的前一个
#-------------------------------------------------------------------------------
def removeNthFromEnd(head, n):
fast, slow = head, head
for i in range(1 + n):
try:
fast = fast.next
except AttributeError:
return head.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head
a = [1, 2, 3, 4, 5]
head = ListNode()
head.add_many(a)
b = removeNthFromEnd(head, 2)
b.show()
#-------------------------------------------------------------------------------
# Name: Linked List Cycle
# Purpose:
#
# Given a linked list, determine if it has a cycle in it.
# Follow up:
# Can you solve it without using extra space?
#-------------------------------------------------------------------------------
def hasCycle(head):
fast, slow = [head]*2 # Enter runner mode with two pointers
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast is slow:
return True
return False
#-------------------------------------------------------------------------------
# Name: Linked List Cycle II
# Purpose:
#
# Given a linked list, return the node where the cycle begins.
# If there is no cycle, return null.
# 当快慢指针相遇的时候，把其中一个重新指向head，
# 然后两个指针同时同速前进，第二次相遇的地方就是cycle起点。
#-------------------------------------------------------------------------------
def hasCycle(head):
fast, slow = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast is slow:
fast = head
while fast is not slow:
fast = fast.next
slow = slow.next
return fast
return None
#-------------------------------------------------------------------------------
# Name: Merge Two Sorted Lists
# Purpose:
# Merge two sorted linked lists and return it as a new list.
# The new list should be made by splicing together the nodes of the first
# two lists.
#-------------------------------------------------------------------------------
def mergeTwoLists(self, l1, l2):
rst = TreeNode(0)
current = rst.next
while l1 and l2:
if l1 < l2:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 if l1 else l2
return rst.next
```
- Add two numbers
```python
#-------------------------------------------------------------------------------
# Name: Add Two Numbers
# Purpose:
# You are given two linked lists representing two non-negative numbers.
# Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
# Output: 7 -> 0 -> 8
#-------------------------------------------------------------------------------
def addTwoNumbers(l1, l2):
current = dummy = ListNode(0)
carry = 0
while l1 or l2:
rst = carry
if l1:
rst += l1.val
l1 = l1.next
if l2:
rst += l2.val
l2 = l2.next
carry = rst / 10
rst %= 10
current.next = ListNode(rst)
current = current.next
current.next = ListNode(1) if carry == 1 else None
return dummy.next
```
- Bypass the limitation
```python
#-------------------------------------------------------------------------------
# Name: Sort List
# Purpose:
# Sort a linked list in O(n log n) time using constant space complexity.
#-------------------------------------------------------------------------------
class Solution:
# @param head, a ListNode
# @return a ListNode
def sortList(self, head):
if head is None or head.next is None:
return head
arr = self.ll_to_lst(head)
head = ListNode(arr[0])
current = head
for x in arr[1:]:
current.next = ListNode(x)
current = current.next
return head
def ll_to_lst(self, head):
rst = []
while head:
rst.append(head.val)
head = head.next
return sorted(rst)
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment