What are the time complexity of finding KTH element from beginning and KTH element from end in a doubly linked list?

Approach :

So, did you try to solve this problem on your own? There is this trick here in the constraints that you cannot solve the problem by using the size property. Otherwise, it would have been a piece of cake, right? So, the solution to this problem is called the Two Pointer Approach and it is not only used in this problem, but it is used in many problems. Let us try to understand the basis of this two pointer approach first in a fun way.

The Idea Behind The Two Pointer Approach:

Let us consider a racing track (500m long). Let us say there are two people. They are you and me. So, my friend, you and I are on a racing track and the race has not started yet. You are already standing at the 200m spot while I am at the starting position i.e. the 0m spot. (Have a look at fig-4)

Input: 1 -> 2 -> 3 -> 4 -> 5, K = 5
Output: 5 -> 2 -> 3 -> 4 -> 1
Explanation: The 5th node from 1st is 5 and 5th node from last is 1, so swap them.

Approach: To solve the problem follow the below idea:

The idea is very simple to find the kth node from the start and the kth node from the last is n-k+1th node from start. Swap both nodes
However, there are some corner cases, which must be handled
Y is next to X
X is next to Y
X and Y are the same
X and Y don’t exist (k is more than the number of nodes in the linked list)

Below is the implementation of the above approach:

#include <bits/stdc++.h>
using namespace std;
typedef struct Node {
    int data;
    struct Node* next;
} Node;
void push(Node** head_ref, int new_data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
void printList(Node* node)
{
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}
int countNodes(struct Node* s)
{
    int count = 0;
    while (s != NULL) {
        count++;
        s = s->next;
    }
    return count;
}
void swapKth(struct Node** head_ref, int k)
{
    int n = countNodes(*head_ref);
    if (n < k)
        return;
    if (2 * k - 1 == n)
        return;
    Node* x = *head_ref;
    Node* x_prev = NULL;
    for (int i = 1; i < k; i++) {
        x_prev = x;
        x = x->next;
    }
    Node* y = *head_ref;
    Node* y_prev = NULL;



    for (int i = 1; i < n - k + 1; i++) {
        y_prev = y;
        y = y->next;
    }
    if (x_prev)
        x_prev->next = y;
    if (y_prev)
        y_prev->next = x;
    Node* temp = x->next;
    x->next = y->next;
    y->next = temp;
    if (k == 1)
        *head_ref = y;
    if (k == n)
        *head_ref = x;
}
int main()
{
    struct Node* head = NULL;
    for (int i = 8; i >= 1; i--)
        push(&head, i);
    cout << "Original Linked List: ";
    printList(head);
    for (int k = 1; k < 9; k++) {
        swapKth(&head, k);
        cout << "\nModified List for k = " << k << endl;
        printList(head);
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node* next;
} Node;
void push(Node** head_ref, int new_data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
void printList(Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}
int countNodes(Node* s)
{
    int count = 0;
    while (s != NULL) {
        count++;
        s = s->next;
    }
    return count;
}
void swapKth(Node** head_ref, int k)
{
    int n = countNodes(*head_ref);
    if (n < k)
        return;
    if (2 * k - 1 == n)
        return;
    Node* x = *head_ref;
    Node* x_prev = NULL;
    for (int i = 1; i < k; i++) {
        x_prev = x;
        x = x->next;
    }
    Node* y = *head_ref;
    Node* y_prev = NULL;
    for (int i = 1; i < n - k + 1; i++) {
        y_prev = y;
        y = y->next;
    }
    if (x_prev)
        x_prev->next = y;
    if (y_prev)
        y_prev->next = x;
    Node* temp = x->next;
    x->next = y->next;
    y->next = temp;
    if (k == 1)
        *head_ref = y;
    if (k == n)
        *head_ref = x;
}
int main()
{
    Node* head = NULL;
    for (int i = 8; i >= 1; i--)
        push(&head, i);
    printf("Original Linked List: ");
    printList(head);
    for (int k = 1; k < 9; k++) {
        swapKth(&head, k);
        printf("\nModified List for k = %d\n", k);
        printList(head);
    }
    return 0;
}

class Node {
    int data;
    Node next;
    Node(int d)
    {
        data = d;
        next = null;
    }
}
class LinkedList {
    Node head;
    void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
    void printList()
    {
        Node node = head;
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println("");
    }
    int countNodes()
    {
        int count = 0;
        Node s = head;
        while (s != null) {
            count++;
            s = s.next;
        }
        return count;
    }
    void swapKth(int k)
    {
        int n = countNodes();
        if (n < k)
            return;
        if (2 * k - 1 == n)
            return;
        Node x = head;
        Node x_prev = null;
        for (int i = 1; i < k; i++) {
            x_prev = x;
            x = x.next;
        }
        Node y = head;
        Node y_prev = null;
        for (int i = 1; i < n - k + 1; i++) {
            y_prev = y;
            y = y.next;
        }
        if (x_prev != null)
            x_prev.next = y;
        if (y_prev != null)
            y_prev.next = x;
        Node temp = x.next;
        x.next = y.next;
        y.next = temp;
        if (k == 1)
            head = y;
        if (k == n)
            head = x;
    }
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
        for (int i = 8; i >= 1; i--)
            llist.push(i);
        System.out.print("Original linked list: ");
        llist.printList();
        System.out.println("");
        for (int i = 1; i < 9; i++) {
            llist.swapKth(i);
            System.out.println("Modified List for k = "
                               + i);
            llist.printList();
            System.out.println("");
        }
    }
}

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
class LinkedList:
    def __init__(self, *args, **kwargs):
        self.head = Node(None)
    def push(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node
    def printList(self):
        node = self.head
        while node.next is not None:
            print(node.data, end=" ")
            node = node.next
    def countNodes(self):
        count = 0
        node = self.head
        while node.next is not None:



            count += 1
            node = node.next
        return count
    def swapKth(self, k):
        n = self.countNodes()
        if n < k:
            return
        if (2 * k - 1) == n:
            return
        x = self.head
        x_prev = Node(None)
        for i in range(k - 1):
            x_prev = x
            x = x.next
        y = self.head
        y_prev = Node(None)
        for i in range(n - k):
            y_prev = y
            y = y.next
        if x_prev is not None:
            x_prev.next = y
        if y_prev is not None:
            y_prev.next = x
        temp = x.next
        x.next = y.next
        y.next = temp
        if k == 1:
            self.head = y
        if k == n:
            self.head = x
if __name__ == "__main__":
    llist = LinkedList()
    for i in range(8, 0, -1):
        llist.push(i)
    llist.printList()
    print("\n")
    for i in range(1, 9):
        llist.swapKth(i)
        print("Modified List for k = ", i)
        llist.printList()
        print("\n")

using System;
public class Node {
    public int data;
    public Node next;
    public Node(int d)
    {
        data = d;
        next = null;
    }
}
public class LinkedList {
    Node head;
    void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
    void printList()
    {
        Node node = head;
        while (node != null) {
            Console.Write(node.data + " ");
            node = node.next;
        }
        Console.WriteLine("");
    }
    int countNodes()
    {
        int count = 0;
        Node s = head;
        while (s != null) {
            count++;
            s = s.next;
        }
        return count;
    }
    void swapKth(int k)
    {
        int n = countNodes();
        if (n < k)
            return;
        if (2 * k - 1 == n)
            return;
        Node x = head;
        Node x_prev = null;
        for (int i = 1; i < k; i++) {
            x_prev = x;
            x = x.next;
        }
        Node y = head;
        Node y_prev = null;
        for (int i = 1; i < n - k + 1; i++) {
            y_prev = y;
            y = y.next;
        }
        if (x_prev != null)
            x_prev.next = y;
        if (y_prev != null)
            y_prev.next = x;
        Node temp = x.next;
        x.next = y.next;
        y.next = temp;
        if (k == 1)
            head = y;
        if (k == n)



            head = x;
    }
    public static void Main(String[] args)
    {
        LinkedList llist = new LinkedList();
        for (int i = 8; i >= 1; i--)
            llist.push(i);
        Console.Write("Original linked list: ");
        llist.printList();
        Console.WriteLine("");
        for (int i = 1; i < 9; i++) {
            llist.swapKth(i);
            Console.WriteLine("Modified List for k = " + i);
            llist.printList();
            Console.WriteLine("");
        }
    }
}

<script>
 class Node {
        constructor(val) {
            this.data = val;
            this.next = null;
        }
    }
    var head;
    function push(new_data) {
         new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
    function printList()
    {
         node = head;
        while (node != null)
        {
            document.write(node.data + " ");
            node = node.next;
        }
        document.write("");
    }
    function countNodes()
    {
        var count = 0;
         s = head;
        while (s != null)
        {
            count++;
            s = s.next;
        }
        return count;
    }
    function swapKth(k)
    {
        var n = countNodes();
        if (n < k)
            return;
        if (2 * k - 1 == n)
            return;
         x = head;
         x_prev = null;
        for (i = 1; i < k; i++)
        {
            x_prev = x;
            x = x.next;
        }
         y = head;
         y_prev = null;
        for (i = 1; i < n - k + 1; i++)
        {
            y_prev = y;
            y = y.next;
        }
        if (x_prev != null)
            x_prev.next = y;
        if (y_prev != null)
            y_prev.next = x;
         temp = x.next;
        x.next = y.next;
        y.next = temp;
        if (k == 1)
            head = y;
        if (k == n)
            head = x;
    }
        for (let i = 8; i >= 1; i--)
            push(i);
        document.write("Original linked list: <br/>");
        printList();
        document.write("<br/>");
        for (let i = 1; i < 9; i++)
        {
            swapKth(i);
            document.write("Modified List for k = " + i + "<br/>");
            printList();
            document.write("<br/>");
        }
</script>

OutputOriginal Linked List: 1 2 3 4 5 6 7 8 Modified List for k = 1 8 2 3 4 5 6 7 1 Modified List for k = 2 8 7 3 4 5 6 2 1 Modified List for k = 3 8 7 6 4 5 3 2 1 Modified List for k = 4 8 7 6 5 4 3 2 1 Modified List for k = 5 8 7 6 4 5 3 2 1 Modified List for k = 6 8 7 3 4 5 6 2 1 Modified List for k = 7 8 2 3 4 5 6 7 1 Modified List for k = 8 1 2 3 4 5 6 7 8

Time Complexity: O(N), where N is the length of the list. One traversal of the list is needed.
Auxiliary Space: O(1). No extra space is required.

Please note that the above code runs three separate loops to count nodes, find x and x prev, and to find y and y_prev. These three things can be done in a single loop. The code uses three loops to keep things simple and readable.