# Singly Linked List

#### Linked List - 101

#### Linked List vs Arrays

#### Basic propperties:

- [x] Print all the nodes in a given linked list.
- [x] Give the length of the linked list
- [x] Print the data at a particular position of the linked list.
- [x] Reverse a linked list.
- [ ] Node swap
- [ ] Remove Duplicates

#### Common Practice Problems:

#### Cycle Detection: Floyd Algo

* [Practice Problem: Given a linked list, determine if it has a cycle in it.](https://leetcode.com/problems/linked-list-cycle/)
---

#### Linked List

class Node:
    def __init__(self, data = 0, next = None):
        self.data = data
        self.next = next

The basic building block of any Linked List is the base class which generally holds two very useful information.

* `self.data`: This is to store the data in the node.
* `self.next`: This acts as a pointer to the next node.

#### Linked List vs Arrays


#### Insertion:

##### **Inserting at the end of the node**

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        # creating a node
        new_node = Node(data)
        
        # Checking if the current head is None
        if self.head is None:
            self.head = new_node
            return

        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

##### **Inserting at the start of th node**

    def prepend(self, data):
        new_node = Node(data)

        new_node.next = self.head
        self.head = new_node

##### **Inserting at the after a given node**

    def insert_after_node(self, prev_node, data):
        if not prev_node:
            return "Previous node is not in the list"

        new_node = Node(data)

        new_node.next = prev_node.next
        prev_node.next = new_node

#### Deletion:

##### **Deleting a particluar node**

class LinkedList:
    def __init__(self):
        self.head = None
    
    def delete_node(self, key):

        cur_node = self.head
        
        # If head of the node is to be deleted
        if cur_node and cur_node.data == key:
            self.head = cur_node.next
            cur_node = None
            return

        prev = None 
        # Iterate and find the node to be delted
        while cur_node and cur_node.data != key:
            prev = cur_node
            cur_node = cur_node.next
        # Node is not in the Linked List
        if cur_node is None:
            return 

        prev.next = cur_node.next
        cur_node = None

##### **Deleting a particluar position**

    def delete_node_at_pos(self, pos):

        cur_node = self.head

        if pos == 0:
            self.head = cur_node.next
            cur_node = None
            return

        prev = None
        count = 0
        while cur_node and count != pos:
            prev = cur_node 
            cur_node = cur_node.next
            count += 1

        if cur_node is None:
            return 

        prev.next = cur_node.next
        cur_node = None

#### Cycle Detection

* For cycle detection we would need two pointers. One would be slow i.e `slowptr` and the other would be fast i.e `fastptr`.
* The `slowptr` moves one position per index and the `fastptr` moves two position per index.
* To check if the LinkedList has a cycle is when the the `fastptr` won't reach the end of the list and would eventually overlap the `slowptr` during the iteration.
* If `slowptr` equals the `fastptr` the given Linked List has a cycle.


def hasCycle(self, head):
    if head is None:
        return False
    
    slowptr = head
    fastptr = head.next
    
    """
    Checking if slowptr, fastptr and fastptr.next values exsits and are not None. 
    Otherwise the increment of slowptr and fastptr would give None and fail.
    """
    while slowptr is not None and fastptr is not None and fastptr.next is not None:
        if slowptr == fastptr:
            return True
        slowptr = slowptr.next
        fastptr = fastptr.next.next
    
    return False