They can be grown & pruned.
What is Linked List?
Linked List is a non-contiguous data structure. The singly linked list is a linear data structure in which each list element contains a pointer that points to the next element in the list. Each element in the singly linked list is called a node. Each node has two components: data and a pointer next which points to the next node in the list. The first node of the list is called a head, and the last node of the list is called a tail. The last node of the list contains a pointer to the null. Each node in the list can be accessed linearly by traversing through the list from head to tail.
Linked List Implementation
We will have a Node class, which has two attributes data, and next.
Node.java
class Node{
int data;
Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}
SingleLinkedList.java
package LinkedList;
public class SingleLinkedList {
//Head of the Linked List
Node head;
public SingleLinkedList(){
this.head = null;
}
/**
* Insert node into linked list.
* -> Iterate through the linked list.
* -> While at last node of the linked list, point the last node to the newly created node.
*/
public void insertIntoLinkedList(int data){
Node newNode = new Node(data);
// If the linked list doesn't contain any nodes.
if(head==null){
head = newNode;
}
else{
Node temp = head;
while(temp.next != null){
temp = temp.next;
}
temp.next = newNode;
}
}
/**
* Insert at head of linked list.
* If head == null, make current node as head.
* else point newly created node.next to head.
* and make new node as head.
*/
public void insertAtHead(int data){
Node newNode = new Node(data);
if(head == null){
head = newNode;
}
else{
newNode.next = head;
head = newNode;
}
}
/**
* To delete a element in the linked list.
* Check if the node.next.data == elementToBeDeleted.
* If true point the cuurent node to next, next node by skipping the the next node.
* else do nothing.
*/
public void deleteInLinkedList(int target){
if(head == null){
System.out.println("Linked list is empty");
}
else{
Node temp = head;
while(temp.next != null){
if(temp.next.data == target){
temp.next = temp.next.next;
}
else{
temp = temp.next;
}
}
}
}
/**
* Traverse the linked list.
*/
public void displayLinkedList(){
if(head==null){
System.out.println("Linked list is empty");
}
else{
Node temp = head;
while(temp!=null){
System.out.print(temp.data +"->");
temp = temp.next;
}
System.out.print("NULL");
}
}
public static void main(String[] args) {
SingleLinkedList list = new SingleLinkedList();
list.insertIntoLinkedList(2);
list.insertIntoLinkedList(3);
list.insertAtHead(1);
list.displayLinkedList();
System.out.println();
list.deleteInLinkedList(2);
list.displayLinkedList();
System.out.println();
list.deleteInLinkedList(3);
list.displayLinkedList();
}
}
Applications of Linked List
- Polynomial Manipulation representation
- Addition of long positive integers
- Representation of sparse matrices
- Addition of long positive integers
- Symbol table creation
- Mailing list
- Memory management
Linked List Patterns for actual interviews.
Two Pointers
A very useful technique for dealing with linked lists involves iterating through the list with 2 or more pointers. The differences between how the pointers to iterate can be used to make calculations on the list more efficient.
Middle of Linked List.
In order to find the middle of the linked list, for the naive method, we get the length of the linked list. Then traverse again through the linked list with the count, if at count == (length of linked list)/2 +1, then return the head.
Time Complexity is O(N)+O(N/2).
O(N) -> For the length of the linked list.
O(N/2) -> For the middle of the linked list.
We can improvise the above solution by using two pointers, maintaining two pointers called fast and slow, moving the fast pointer by two nodes, and the slow pointer by one node. Such that while the fast pointer reaches null, the slow pointer will be pointing to the middle node of the linked list.
Code
class Solution {
public ListNode middleNode(ListNode head) {
if(head==null) return null;
ListNode fast=head, slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
}
In order to find the cycle in the linked list, the brute force will be maintaining a hashmap to store the already visited nodes, If at any point the current node pointed to the node already present in the hashmap, then we return true, else we return false.
Time Complexity is O(N) for traversal of the linked list, and
Space Complexity is O(N) for hashmap to store the already visited nodes.
An efficient way of solving this problem is achieved by using the two-pointer technique.
We maintain two pointers called fast and slow pointing towards the head, and we move the fast pointer by two nodes and the slow pointer by one node. The intuition behind this solution is that, If the given linked list contains a cycle, at any point we will reach a moment where fast equals slow.
Code
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null) return false;
ListNode fast=head, slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow) return true;
}
return false;
}
}
Reverse Pattern
The brute force solution will be, we traverse through the Linked List and store the values in the data structure, iterate again the Linked List, and modify the values at each node.
Time Complexity will be O(N) + O(N) for the 2 traversals of Linked List.
Space Complexity will be O(N) for storing the values of the nodes.
An efficient way of solving this will be based on modifying the node pointers. Maintain three-pointers, called previous(for the previous node) and toNext(for the next node pointer), while iterating through the linked list, point the toNext to current node next, current next to previous, previous to current, and current to toNext.
Code
class Solution {
public ListNode reverseList(ListNode head) {
ListNode previous = null, toNext = null;
while(head!=null){
toNext = head.next;
head.next = previous;
previous = head;
head = toNext;
}
return previous;
}
}
Same as above, we reverse the linked list but we reverse in between from m from starting and n from ending.
Code
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// Empty list
if (head == null) {
return null;
}
// Move the two-pointers until they reach the proper starting point
// in the list.
ListNode cur = head, prev = null;
while (m > 1) {
prev = cur;
cur = cur.next;
m--;
n--;
}
// The two pointers that will fix the final connections.
ListNode con = prev, tail = cur;
// Iteratively reverse the nodes until n becomes 0.
ListNode third = null;
while (n > 0) {
third = cur.next;
cur.next = prev;
prev = cur;
cur = third;
n--;
}
// Adjust the final connections as explained in the algorithm
if (con != null) {
con.next = prev;
} else {
head = prev;
}
tail.next = cur;
return head;
}
}
The brute force way of solving this problem is to store all the values in the data structure (Array or ArrayList) and check if the array is palindrome or not.
An efficient way of solving this problem is achieved by reversing a linked list from the middle element, such that we can see if the first half of nodes and middle nodes possess the same data.
Code
class Solution {
private ListNode reverse(ListNode node){
//Edge Case
if(node==null || node.next==null){
return node;
}
ListNode previous=null, toNext=null;
while(node != null){
toNext = node.next;
node.next = previous;
previous = node;
node = toNext;
}
return previous;
}
public boolean isPalindrome(ListNode node) {
//Edge Cases
if(node==null) return false;
if(node.next==null) return true;
ListNode slow=node, fast=node;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==null){
break;
}
}
slow = reverse(slow);
while(node!=null && slow!=null){
if(node.data != slow.data){
return false;
}
node = node.next;
slow = slow.next;
}
return true;
}
}
In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.
For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.
The brute force solution for this problem will be traversing through the linked list, and storing all the values in the array, then traversing the array using the two pointer approach(i.e I from 0 and j from the array.length-1), and updating the maxSum for every array[i]+array[j].
Time Complexity will be O(N) + O(N)
Space Complexity will be O(N)
An efficient way of solving this problem was to reverse the linked list from the middle, such that while traversing again from the head, and middle node of the linked list, and update the maxSum with the sum of the head node's data and middle node's data.
Code
class Solution {
public int pairSum(ListNode head) {
if (head == null) {
return 0;
}
if (head.next == null) {
return head.data;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
slow = reverse(slow);
fast = head;
int sum = Integer.MIN_VALUE;
while (slow != null) {
sum = Math.max(slow.val + fast.val, sum);
slow = slow.next;
fast = fast.next;
}
return sum;
}
public ListNode reverse(ListNode node) {
if (node == null) {
return null;
}
ListNode current = node;
ListNode previous = null;
while (current != null) {
ListNode next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}
}
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. K is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
The intuition behind this solution was to reverse the first k groups recursively, and then call the function for the next nodes.
Code
class Solution {
public Node reverseKGroup(Node head, int k) {
//Edge Cases
if(head==null || head.next==null || k==1)
return head;
Node temp = head;
int sz = 0;
while(temp != null){
sz++;
temp = temp.next;
}
if(sz < k){
return head;
}
Node previous=null, toNext=null, current=head;
int count=0;
while(current!=null && count<k){
toNext=current.next;
current.next=previous;
previous=current;
current=toNext;
count+=1;
}
if(toNext!=null){
head.next = reverseKGroup(toNext, k);
}
return previous;
}
}
Traversal Pattern
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
The intuition behind this solution was to iterate over the linked list l1 and l2, and we add the two node values along with carry, add this new node with sum(l1.data+l2.data+carry%10) to the new Linked List, and update the carry by dividing with 10.
Code
class Solution {
public Node addTwoNumbers(Node l1, Node l2) {
Node dummyHead = new Node(0);
Node curr = dummyHead;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int x = (l1 != null) ? l1.value : 0;
int y = (l2 != null) ? l2.value : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new Node(sum % 10);
curr = curr.next;
if (l1 != null)
l1 = l1.next;
if (l2 != null)
l2 = l2.next;
}
return dummyHead.next;
}
}
Everything is the same as above, but we reverse the given two linked lists, and while returning the output, we reverse that too.
Code
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverse(l1);
l2 = reverse(l2);
ListNode ans = new ListNode(-1);
ListNode pointer = ans;
ListNode curr1 = l1;
ListNode curr2 = l2;
int carry = 0;
while(curr1 != null || curr2 != null || carry !=0){
ListNode n = new ListNode();
int num = carry + (curr1 != null ? curr1.val : 0) + (curr2 != null ? curr2.val : 0) ;
if(num>=10){
num = num -10;
carry =1;
}
else{
carry = 0;
}
n.val = num;
pointer.next = n;
pointer = pointer.next;
if(curr1!=null) curr1 = curr1.next;
if(curr2!=null) curr2 = curr2.next;
}
ans = reverse(ans.next);
return ans;
}
public ListNode reverse(ListNode head){
ListNode curr = head;
ListNode prev =null;
ListNode temp;
while(curr != null){
temp = curr.next;
curr.next = prev;
prev= curr;
curr = temp;
}
return prev;
}
}
Delete Duplicates in Sorted Linked List
Given the head of a sorted linked list, delete all duplicates such that each element appears only once.
The intuition behind this solution is to, check If the next node's values to the current node, are equal or not, if they are equal, skip the next node, else move the current by one node.
Code
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode list = head;
while(list != null) {
if (list.next == null) {
break;
}
if (list.val == list.next.val) {
list.next = list.next.next;
} else {
list = list.next;
}
}
return head;
}
}