Problem: Is linked list a palindrome?

​leetcode.com/problems/palindrome-linked-list/submissions/

SOLUTION

Store the characters int he array and use two pointer method to check if it is a plaindrome

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        arr = []
        walker = head
        while walker!=None:
            arr.append(walker.val)
            walker = walker.next
        
        i = 0
        j = len(arr)-1
        while(i < j):
            if arr[i]!=arr[j]:
                return False
            i+=1
            j-=1
        return True
                

Problem: Detect Linked List Cycle

​leetcode.com/problems/linked-list-cycle/

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 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

SOLUTION:
it's important to clarity if the values in the linked list can repeat, in this case they can 
keep a running set of visited nodes
walk through linked list checking at each node if it is in the visited set

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        visited = set()
        walker = head
    
        while walker is not None:
            if walker in visited:
                return True
            visited.add(walker)
            walker = walker.next
        
        return False