In preparing for the coding interview, I will start writing blogs to record the hints and tips about the basic data structures. The series of the blog will start from Linked List in this one.
Definition:
According to the book, Cracking the Coding Interview, a linked list is a data structure that represents a sequence of nodes where each node stores a value and points to next node.
diagram
Unlike array, linked list didn’t allow constant time access to a particular “index” within the list. When you have to find the (k)-th element in the list, you have to iterate through k elements.
The advantage of using Linked List is that items could be added or removed from the head in constant time.
A Linked List Node
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def appendToTail(self, x):
end = ListNode(x) # declare an end node
while self.next: # iterate to the current ending node
self = self.next
self.next = end # let the current ending node point to the new ending nodeif __name__ == '__main__':
A = ListNode(1)
A.appendToTail(2)
A.appendToTail(3)
A.appendToTail(4)
print(A.val) # 1st element
print(A.next.val) # 2nd element
print(A.next.next.val) # 3rd element
print(A.next.next.next.val) # 4th element
## 1
## 2
## 3
## 4Some Basic Manipulation of Linked List
1. Remove node from Linked List
You are given a linked list with much more than one element and an integer Then the task is to write a function that is able to remove the node whose stored value match the given integer.
Test the value stored in the next node, when the value matched replace the next node by the more next one.
# remove the node from linked list
class Solution:
def removeNode(self, head, value):
if head.val == value:
return head.next
tmp = head
while tmp.next:
if tmp.next.val == value:
tmp.next = tmp.next.next
else:
tmp = tmp.next
return headif __name__ == '__main__':
A = ListNode(2)
A.appendToTail(2)
A.appendToTail(1)
ans = Solution().removeNode(A, 1)
print(ans.next.next) # None: 1 has been removed## None2. print kth-to-last element in the Linked List
You are given a linked list and the task is to write a function to return the kth elment to last.
# two pointers: keep the difference between two pointers within k-1
class Solution:
def KthNodeToLast(self, head, k):
diff = 0
head2 = head
while head.next:
diff += 1
head = head.next
if diff >= k:
head2 = head2.next
return head2if __name__ == '__main__':
A = ListNode(1)
A.appendToTail(2)
A.appendToTail(1) # A = [1, 2, 1]
print(Solution().KthNodeToLast(A, 1).val) # 1## 13. Print the Middle node in the Linked List
Following the last problem, define an index for the first pointer and make sure the index of the second pointer is half to the first one’s
# keep the index of second pointer half to the first pointer
class Solution:
def middleNodeInList(self, head):
index = 0
tmp = head
while head.next:
index += 1
head = head.next
if index > 0 and index % 2 == 0:
tmp = tmp.next
return tmpif __name__ == '__main__':
A = ListNode(1)
A.appendToTail(2)
A.appendToTail(1)
A.appendToTail(3)
A.appendToTail(4) # A = [1, 2, 1, 3, 4]
print(Solution().middleNodeInList(A).val) # 1## 14.(Advanced) Delete the node in the middle
You are given one Linked List, build a function to delete the node in the middle of the list
class Solution:
def deleteMiddle(self, head):
index = 0
current = head
middle = head
pre = ListNode(None)
pre.next = head
while current.next:
index += 1
if index > 0 and index % 2 == 0:
middle = middle.next
pre = pre.next
current = current.next
pre.next = pre.next.next
return headif __name__ == '__main__':
A = ListNode(1)
A.appendToTail(2)
A.appendToTail(1)
ans = Solution().deleteMiddle(A)
print(A.val) # 1
print(A.next.val) # 1## 1
## 1
近期评论