1. Convert Binary Number in a Linked List to Integer

From 1290. Convert Binary Number in a Linked List to Integer

1.1 Problem Description

Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.

Return the decimal value of the number in the linked list.

Example

img 

Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10

1.2 Solution

  1. Try to store head value in string format
  2. Then use int() method to turn binary to decimal
class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
      	#create str s to store value
        s = ""
        
        # while loop until linked list ends
        while head:
          s += str(head.val)
          head = head.next
        
        return int(s,2) #base is 2, binary to decimal

2. Middle of the Linked List

From 876. Middle of the Linked List

2.1 Problem Description

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example

img 

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

2.2 Solution

A smart way is to use 2 pointers, slow and fast, each time slow goes 1 step while fast goes 2 step, hence when fast hits the end, slow will point to the middle of the linked list.

def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
  			# create 2 pointers
        slow = fast = head
      
      	# while fast has not hit the end
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # slow will point the middle of the linked list
        return slow

3. “Delete” Node in a Linked List

From 237. Delete Node in a Linked List

3.1 Problem Description

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

Example

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

3.2 Solution

Actually you can not really delete a node, you just skip this node and point to the next.

class Solution:
    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

4. Reverse Linked List

From 206. Reverse Linked List

4.1 Problem Description

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

4.2 Solution

The idea is to give next value to previous value.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur, prev = head, None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        return prev

5. Palindrome Linked List

From 234. Palindrome Linked List

5.1 Problem Description

Given the head of a singly linked list, return true if it is a palindrome.

Example

img 

Input: head = [1,2,2,1]
Output: true

5.2 Solution

We can combine what we learned in 206. Reverse Linked List, first we try to get the reverse first half of linked list using slow and fast pointers, and then compare the value of the first half linked list with the second half of the linked list.

def isPalindrome(self, head):
    fast = slow = head
    # find the mid node, slow will point to the mid node
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    # reverse the second half
    node = None
    while slow:
        nxt = slow.next
        slow.next = node
        node = slow
        slow = nxt
    # compare the first and second half nodes
    while node: # while node and head:
        if node.val != head.val:
            return False
        node = node.next
        head = head.next
    return True

6. Linked List Cycle

From 141. Linked List Cycle

6.1 Problem Description

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example

6.2 Solution

The idea is similar to 876. Middle of the Linked List, we can use slow and fast pointers to tackle this problem.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        try:
            slow = head
            fast = head.next
            while slow is not fast:
                slow = slow.next
                fast = fast.next.next
            return True
        
        except:
            return False