Intro to Linked Lists in C++

A linked list is a linear data structure where each element is a separate object.
Linked list elements are not stored at contiguous locations; the elements are linked using pointers.

Each node of a list is made up of two items — the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that the head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

An example of a linked list node with integer data.

// Linked list example in C/C++
// A linked list node
struct ListNode
{
  int val;
  struct ListNode *next;
};

Arrays vs Linked Lists

Arrays and Linked Lists both are linear data structures, but they both have some advantages and disadvantages over each other.

One advantage of the linked list is that elements can be added to it indefinitely, while an array will eventually get filled or have to be resized (a costly operation that isn’t always possible).

Elements are also easily removed from a linked list whereas removing elements from an array leaves empty spaces that are a waste of computer memory.

Insertion in Array and Linked List

However, unlike arrays which allow random access to the elements contained within them, a link list only allows sequential access to its elements. Linked lists also use more storage space in a computer’s memory as each node in the list contains both a data item and a reference to the next node.

It follows that linked lists should be used for large lists of data where the total number of items in the list is changing. Arrays, on the other hand, are better suited to small lists, where the maximum number of items that could be on the list is known.

Question 1: Intersection of Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3

begin to intersect at node c1.

Note: Should preferably run in O(n) time and use only O(1) memory

Solution:

• Check the difference ‘d’ in the length of Linked Lists
• Move ahead ‘d’ steps in the longer Linked List

int getLength(ListNode *head) {
            int ret = 0;
            while (head) {
                ret++;
                head = head->next;
            }
            return ret;
        }

        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if(!headA || !headB)
                return NULL;
            int lenA = getLength(headA), lenB = getLength(headB);
            int lenDiff = lenA - lenB;
            ListNode *pa = headA;
            ListNode *pb = headB;
            if(lenDiff > 0) {
                while(lenDiff != 0) {
                    pa = pa->next;
                    lenDiff--;
                }
            }
            else if(lenDiff < 0) {
                while(lenDiff != 0) {
                    pb = pb->next;
                    lenDiff++;
                }
            }
            while(pa && pb) {
                if(pa == pb)
                    return pa;
                pa = pa->next;
                pb = pb->next;
            }
            return NULL;
        }

Question 2: Reverse a Linked List (Iterative)

Reverse a linked list. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL,

return 5->4->3->2->1->NULL.

Solution:

List Sort Questions

Question 3: Sort Binary Linked List

Given a Linked List A consisting of N nodes.

The Linked List is binary i.e data values in the linked list nodes consist of only 0’s and 1's.

You need to sort the linked list and return the new linked list.

NOTE: Try to do it in constant space.

Example Input

Input 1:

1 -> 0 -> 0 -> 1

Input 2:

0 -> 0 -> 1 -> 1 -> 1

Example Output

Output 1:

0 -> 0 -> 1 -> 1

Output 2:

0 -> 0 -> 0 -> 1 -> 1

Example Explanation

Explanation 1:

The sorted linked list looks like:
  0 -> 0 -> 1 -> 1

Explanation 2:

The sorted linked list looks like:
  0 -> 0 -> 0 -> 1 -> 1

Solution:

The following steps can be used to sort the given linked list:

1. Traverse the list and count the number of 0s, 1s. Let the counts be n1, n2 respectively.
2. Traverse the list again, fill the first n1 nodes with 0, then n2 nodes with 1.

Time Complexity: O(N) where N is the number of nodes in the linked list.
Auxiliary Space: O(1)

The above solution does not work when these values have associated data with them.
For example, these two represent two colors and different types of objects associated with the colors and we want to sort objects (connected with a linked list) based on colors.

So, A new solution is discussed that works by changing links.

Iterate through the linked list. Maintain 2 pointers named zero and one to point to current ending nodes of linked lists containing 0 and 1 respectively.
For every traversed node, we attach it to the end of its corresponding list.
Finally, we link both the lists.

To avoid many null checks, we use two dummy pointers dummy1and dummy2that work as dummy headers of the two lists.

Time Complexity: O(N) where N is the number of nodes in the linked list.
Auxiliary Space: O(1)

ListNode* Solution::solve(ListNode* head) {
    ListNode dummy1(0);
    ListNode* zero = &dummy1;
    ListNode dummy2(0);
    ListNode* one = &dummy2;
    
    while(head){
        if(head->val == 0){
            zero->next = head;
            zero = zero->next;
            head = head->next;
        }
        else if(head->val == 1){
            one->next = head;
            one = one->next;
            head = head->next;
        }
    }
    one->next = NULL;
    zero->next = dummy2.next;
    return dummy1.next;
}

List 2 Pointer Questions

Question 4: Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Solution:

You need to change next pointer of some element to next different element. Take care of corner cases if any.

Skip the node where head->next != NULL && head->val == head->next->val.

Make sure you take care of corner cases :
1) Do you handle repetitions at the end ? ex : 1 -> 1
2) Do you handle cases where there is just one element ? ex : 1
3) Do you handle cases where there is just one element repeated numerous times ? 1->1->1->1->1->1

ListNode *deleteDuplicates(ListNode *head) {
        ListNode *origin = head;
            while (head != NULL) {
                    while(head->next != NULL && head->val == head->next->val) {
                            head->next = head->next->next;
                    }
                    head = head->next;
            }
            return origin;
}

Pointer Move Questions

Question 5: Even Reverse

Given a linked list A , reverse the order of all nodes at even positions.

Example Input

Input 1:

A = 1 -> 2 -> 3 -> 4

Input 2:

A = 1 -> 2 -> 3

Example Output

Output 1:

1 -> 4 -> 3 -> 2

Output 2:

1 -> 2 -> 3

Example Explanation

Explanation 1:

Nodes are positions 2 and 4 have been swapped.

Explanation 2:

No swapping neccassary here.

Solution:

Store the even positioned and odd positioned nodes in 2 vectors. now reverse the even position vectors and then Recombine them to form a linked list.
All of this will happen in O(n) time.

ListNode* Solution::solve(ListNode* A) {
    vector<int> v;
    ListNode *ptr = A->next;
    while (ptr != nullptr)
    {
        v.push_back(ptr->val);
        if (ptr->next != nullptr)
        {
            ptr = ptr->next->next;
        }
        else
        {
            ptr = ptr->next;
        }
    }
    reverse(v.begin(), v.end());
    ptr = A->next;
    int i = 0;
    while (ptr != nullptr)
    {
        ptr->val = v[i++];
        if (ptr->next != nullptr)
        {
            ptr = ptr->next->next;
        }
        else
        {
            ptr = ptr->next;
        }
    }
    return A;
}

List Trick Questions

Question 6: Kth Node From Middle

Given a linked list A of length N and an integer B.

You need to find the value of the Bth node from the middle towards the beginning of the Linked List A.

If no such element exists, then return -1.

NOTE:

• Position of middle node is: (N/2)+1, where N is the total number of nodes in the list.

Example Input

Input 1:

A = 3 -> 4 -> 7 -> 5 -> 6 -> 1 6 -> 15 -> 61 -> 16
B = 3

Input 2:

A = 1 -> 14 -> 6 -> 16 -> 4 -> 10
B = 2

Input 3:

A = 1 -> 14 -> 6 -> 16 -> 4 -> 10
B = 10

Example Output

Output 1:

4

Output 2:

14

Output 3:

-1

Example Explanation

Explanation 1:

The Middle of the linked list is the node with value 6.
 The 1st node from the middle of the linked list is the node with value 5.
 The 2nd node from the middle of the linked list is the node with value 7.
 The 3rd node from the middle of the linked list is the node with value 4.
 So we will output 4.

Explanation 2:

The Middle of the linked list is the node with value 16.
 The 1st node from the middle of the linked list is the node with value 6.
 The 2nd node from the middle of the linked list is the node with value 14.
 So we will output 14.

Explanation 3:

The Middle of the linked list is the node with value 16.
There are only 3 nodes to the left of the middle node and we need to find the 10th node which doesn't exist so we will return -1.

Solution:

Find the length of the linked list suppose length is N then you need to find the node at (N/2 + 1 — k)th position from the head of the List.

Traverse the List from beginning to end and count the total number of nodes.
Now, suppose N is the total number of nodes in the List. Therefore, the middle node will be at the position (N/2)+1.
Now, the task remains to print the node at (N/2 + 1 — k)th position from the head of the List.
Algorithm:
(1) Initialize count = 0
(2) Loop through the link list
(2.1) if count is equal to the passed index(i.e N/2 + 1 -k) then return current node
(2.2) Increment count
(2.3) Change current to point to next of the current.

Time Complexity: O(N), where N is the length of the list.
Auxiliary Space: O(1)

int Solution::solve(ListNode* A, int B) {
    int n = 0;
    ListNode *ptr = A;
    while (ptr != nullptr)
    {
        ptr = ptr->next;
        ++n;
    }
    int mid = (n / 2) + 1;
    mid = mid - B - 1;
    if (mid < 0)
    {
        return -1;
    }
    while (mid--)
    {
        A = A->next;
    }
    return A->val;
}

List Math Questions

Question 7: List Cycle

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Try solving it using constant additional space.

Example :

Input : 
                  ______
                 |     |
                 \/    |
        1 -> 2 -> 3 -> 4
Return the node corresponding to node 3.

Solution:

Lets first look at detection of a cycle in the list.

Following are different ways of doing this

1. Use Hashing:
   What if you could maintain a list of nodes already visited. As soon as you visit a node already visited, you know that there is a cycle.

Complexity Analysis:

• Time complexity: O(n).
  Only one traversal of the loop is needed.
• Auxiliary Space: O(n).
  n is the space required to store the value in hashmap.

2) 2 pointer approach ( Floyd’s Cycle-Finding Algorithm ) :
What if you have 2 pointers which are going at different speed. For arguments sake, lets just say one pointer is going at double the speed of the other.

If you detect a cycle, the meeting point is definitely a point within the cycle.

• Can you determine the size of the cycle ? Let the size be k.
• Fix one pointer on the head, and another pointer to kth node from head.
• Now move them simulataneously one step at a time. They will meet at the starting point of the cycle.

Complexity Analysis:

• Time complexity: O(n).
  Only one traversal of the loop is needed.
• Auxiliary Space:O(1).
  There is no space required.

Distance traveled by fast pointer = 2 * (Distance traveled 
                                         by slow pointer)

(m + n*x + k) = 2*(m + n*y + k)

Note that before meeting the point shown above, fast
was moving at twice speed.

x -->  Number of complete cyclic rounds made by 
       fast pointer before they meet first time

y -->  Number of complete cyclic rounds made by 
       slow pointer before they meet first time

From the above equation, we can conclude below

m + k = (x-2y)*n

Which means m+k is a multiple of n.

So if we start moving both pointers again at the same speed such that one pointer (say slow) begins from the head node of the linked list and other pointers (say fast) begins from the meeting point. When the slow pointer reaches the beginning of the loop (has made m steps), the fast pointer would have made also moved m steps as they are now moving the same pace. Since m+k is a multiple of n and fast starts from k, they would meet at the beginning. Can they meet before also? No, because the slow pointer enters the cycle first time after m steps.

ListNode *detectCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) return NULL;

        ListNode* firstp = head;
        ListNode* secondp = head;
        bool isCycle = false;

        while(firstp != NULL && secondp != NULL) {
            firstp = firstp->next;
            if (secondp->next == NULL) return NULL;
            secondp = secondp->next->next;
            if (firstp == secondp) { isCycle = true; break; }
        }

        if(!isCycle) return NULL;
        firstp = head;
        while( firstp != secondp) {
            firstp = firstp->next;
            secondp = secondp->next;
        }

        return firstp;

        
    }