CareerCup

struct node
{
int data;
node *next;
};

void swapfirst_and_last_kth_node(node **head,int k)
{
node *p1=*head,*p2=*head;
while(p1!=NULL && k>1)
{
(p1)=(p1)->next;
k--;
}
if(k!=0 && (p1)==NULL)
{
cout<<"\n Error in the code";
return ;
}
node *p3=p1;
while((p1->next))
{
(p2)=(p2)->next;
(p1)=(p1)->next;
}
int tm=(p3)->data;
(p3)->data=(p2)->data;
(p2)->data=tm;

}

First finding the nth node from end
then traversing upto nth node from start
then swaping data of both the nodes found above.

internal void SwapKthnodefromFirstandKthNodefromlast(int n)
{
if (head == null || n < 1)
return;
Node p1 = head;
Node p2 = head;
for (int i = 0; i < n; i++)
p1 = p1.next;
while (p1 != null)
{
p1 = p1.next;
p2 = p2.next;
}
p1 = head;
for (int i = 0; i < n-1; i++)
{
p1 = p1.next;
}
int temp = p1.data;
p1.data = p2.data;
p2.data = temp;
p1= head;
while (p1!= null)
{
Console.WriteLine(p1.data);
p1= p1.next;
}

}

1. First locate the kth node from start and end.
a. To find the kth node from last - take two pointers pointing to head. Move 1 pointer till kth position. Then move both the pointers together till the first pointer meets the last position. At this time 2nd pointer will be pointing to the kth node from last.
b. To find the kth node from first - Move a pointer to kth position by following link k-1 times.
2. Swap the nodes.

1. Identify kth element from beginning (say kth_first), also reverse the list.
2. Identify kth element from beginning on the reversed link list (say kth_last), and reverse the reversed list (Now the list will become original list).
3. swap the values in kth_first and kth_last.

Logic is in swap_kth_node() function. O(n) time complexity.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    struct Node *next;
    int val;
} Node;

Node *reverse_get_kth_element(Node **head, int k)
{
    Node *kth_element = NULL, *curr = *head, *prev = NULL;
    int i = 0;
    while (curr) {
        i++;
        if (i == k)
            kth_element = curr;

        Node *tmp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = tmp;
    }

    *head = prev; /* prev will be tail of original list */
    return kth_element;
}

void swap_kth_node(Node *head, int k)
{
    /* 1. find kth from first, reverse on the way */
    Node *kth_first = reverse_get_kth_element(&head, k);

    /* 2. find kth from last, reverse on the way. Then we have original list */
    Node *kth_last = reverse_get_kth_element(&head, k);

    //swap kth_first and kth_last
    int tmp_val = kth_first->val;
    kth_first->val = kth_last->val;
    kth_last->val = tmp_val;
}

Node * create_node(int val)
{
    Node *p = (Node *) malloc(sizeof(Node));
    p->next = NULL;
    p->val = val;
    return p;
}

void print_list(Node *head)
{
    printf("List is: ");
    while (head) {
        printf("%d ",head->val);
        head = head->next;
    }
    printf("\n");
}

int main()
{
    Node *head = create_node(1);
    head->next = create_node(2);
    head->next->next = create_node(3);
    head->next->next->next = create_node(4);
    head->next->next->next->next = create_node(5);
    head->next->next->next->next->next = create_node(6);
    head->next->next->next->next->next->next = create_node(7);

    print_list(head); /* 1 2 3 4 5 6 7 */

    swap_kth_node(head, 3);

    print_list(head); /* 1 2 5 4 3 6 7 */
}

/**
 * @author hissar
 */
import java.security.InvalidParameterException;

public class KthNodeSwap {

	public static <T> void swapKthNodes (LinkedNode<T> head, int k) {
		if (head == null)
			throw new NullPointerException ("Empty list");
		if (k == 0)
			throw new InvalidParameterException ("Invalid value of k");
		
		LinkedNode<T> kth = null;
		LinkedNode<T> front = null;
		LinkedNode<T> track = head;
		
		while (track != null) {
			k--;
			if (k == 0) {
				kth = head;
				front = track;
				break;
			}
			track = track.next;
		}
		if (k != 0 || track == null)
			throw new NullPointerException ("In-sufficient no. of Nodes");
		
		while (track.next != null) {
			track = track.next;
			kth = kth.next;
		}
		
		// Perform the swap
		T data = front.data;
		front.data = kth.data;
		kth.data = data;
	}
	
	public static void main(String[] args) {
		LinkedNode<Integer> head = new LinkedNode<Integer>(1);
		LinkedNode<Integer> track = head;
		for (int i = 2; i < 8; i++) {
			track.next = new LinkedNode<Integer>(i);
			track = track.next;
		}
		swapKthNodes (head, 3);
		while (head != null) {
			System.out.println(head.data.intValue());
			head = head.next;
		}
	}
}

public static void swap(LinkedList<Integer> l, int k) {
		
		int tmp = l.get(k-1);
		l.set(k-1, l.get(l.size()-k));
		l.set(l.size()-k, tmp);
	}

public void swapKthNode(Node head, int k){
Node kthFormBeg = head, kthFromEnd = head, temp = head;
int count = 1;
while(temp!=null){
if(count<=k){
kthFormBeg = kthFormBeg.getNext();
temp = temp.getNext();
count++;
}else{
temp = temp.getNext();
kthFromEnd = kthFromEnd.getNext();
}
}
//swap data between nodes
int t = kthFormBeg.getData();
kthFormBeg.setData(kthFromEnd.getData());
kthFromEnd.setData(t);
printList();
}

public void swapKthNode(Node head, int k){
		Node kthFormBeg = head, kthFromEnd = head, temp = head;
		int count = 1;
		while(temp!=null){
			if(count<=k){
				kthFormBeg = kthFormBeg.getNext();
				temp = temp.getNext();
				count++;
			}else{
				temp = temp.getNext();
				kthFromEnd = kthFromEnd.getNext();
			}			
		}
		//swap data between nodes
		int t = kthFormBeg.getData();
		kthFormBeg.setData(kthFromEnd.getData());
		kthFromEnd.setData(t);
		printList();

}