Summary of Linked List.
LeetCode 203 Remove Linked List Elements
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy_head = ListNode(next=head)
cur = dummy_head
while cur.next != None:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy_head.next
LeetCode 707 Design Linked List
class ListNode:
def __init__(self,x):
self.val = x
self.next = None
class MyLinkedList(object):
def __init__(self):
self.size = 0
self.head = ListNode(0) # pseudo head
def get(self, index):
"""
:type index: int
:rtype: int
"""
if index < 0 or index >= self.size:
return -1
cur = self.head
for _ in range(index + 1):
cur = cur.next
return cur.val
def addAtHead(self, val):
"""
:type val: int
:rtype: None
"""
self.addAtIndex(0, val)
def addAtTail(self, val):
"""
:type val: int
:rtype: None
"""
self.addAtIndex(self.size, val)
def addAtIndex(self, index, val):
"""
:type index: int
:type val: int
:rtype: None
"""
if index > self.size:
return
if index < 0:
index = 0
self.size += 1 # update the size
pred = self.head
for _ in range(index): # find the node
pred = pred.next
newNode = ListNode(val) # creat a new node
newNode.next = pred.next # add the new node
pred.next = newNode
def deleteAtIndex(self, index):
"""
:type index: int
:rtype: None
"""
if index < 0 or index >= self.size:
return
self.size -= 1 # update the size
pred = self.head
for _ in range(index): # find the node
pred = pred.next
pred.next = pred.next.next # delete the node
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)
LeetCode 206 Reverse the linked list
class Solution:
def ReverseList(self , head: ListNode) -> ListNode:
if not head:
return head
cur = head
pre = None
while cur:
nxt = cur.next # store the next value
cur.next = pre # point cur.next to pre
pre = cur # move pre to cur
cur = nxt # move cur to cur.next
return pre
LeetCode 24 Swap Nodes in Pairs
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
res = ListNode(next=head)
pre = res
while pre.next and pre.next.next:
cur = pre.next
post = pre.next.next
cur.next = post.next
post.next = cur
pre.next = post
pre = pre.next.next
return res.next
LeetCode 19 Remove Nth Node From End of List
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
length = 0
cur = head
while cur:
length += 1
cur = cur.next # do not use head directly here
dum = ListNode(0,head)
cur = dum
for i in range(1, length - n + 1):
cur = cur.next
cur.next = cur.next.next
return dum.next
LeetCode 160 Intersection of Two Linked Lists
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
a, b = headA, headB
while a!=b:
a = a.next if a else headB
b = b.next if b else headA
return a
LeetCode 142 Linked List Cycle II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
p = head
q = slow
while q != p:
p = p.next
q = q.next
return p
