Imagine your grandpa wants to set up a gathering with all his old friends from school. But he only knows his best friend Jack’s address. Jack only remembers his classmate Rose’s address. Rose only knows her best friend Julie’s address. Julie only knows someone else’s address. The list goes on until the last person, who doesn’t remember anyone’s address and therefore points to a null address. This way, all your grandpa’s friends are able to be notified and attend the gathering. This, in layman’s terms, is how a singly linked list is structured.
A singly linked list is a data structure made of a list of node objects. Each node contains a value itself and a next, which is a pointer that contains the address of the next node object. The head is a pointer that points to the first node object, and the last node object points to None. All these node objects are spread out in different places in the computer’s memory, like the addresses of your grandpa’s friends in the example above.
Below are some leetcode problems of the singly linked list.
https://leetcode.com/problems/reverse-linked-list/
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
before = None
temp = head
while temp:
after = temp.next
temp.next = before
before = temp
temp = after
return before
https://leetcode.com/problems/middle-of-the-linked-list/
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
https://leetcode.com/problems/remove-linked-list-elements/
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
prev = dummy
curr = head
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return dummy.next