Reputation: 6050
Singly linked list in java
i just found this difficult interview question online and I was hoping someone could help me make sense of it. It is a generic question...given a singly linked list, swap each element of the list in pairs so that 1->2->3->4 would become 2->1->4->3.
You have to swap the elements, not the values. The answer should work for circular lists where the tail is pointing back to the head of the list. You do not have to check if the tail points to an intermediate (non-head) element.
So, I thought:
public class Node
{
public int n; // value
public Node next; // pointer to next node
}
What is the best way to implement this? Can anyone help?
Upvotes: 9
Views: 13729
Answers (10)
Reputation: 1
//2.1 , 2.2 Crack the code interview
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
struct Node{
int info;
struct Node *next;
};
struct Node *insert(struct Node *head,int data){
struct Node *temp,*ptr;
temp = (struct Node*)malloc(sizeof(struct Node));
temp->info=data;
temp->next=NULL;
if(head==NULL)
head=temp;
else{
ptr=head;
while(ptr->next!=NULL)
{
ptr=ptr->next;
}
ptr->next=temp;
}
return head;
}
struct Node* reverse(struct Node* head){
struct Node *current,*prev,*next;
current = head;
prev=NULL;
while(current!=NULL){
next=current->next;
current->next = prev;
prev=current;
current=next;
}
head=prev;
return head;
}
/*nth till last element in linked list*/
void nthlastElement(struct Node *head,int n){
struct Node *ptr;
int last=0,i;
ptr=head;
while(ptr!=NULL){
last++;
//printf("%d\n",last);
ptr=ptr->next;
}
ptr=head;
for(i=0;i<n-1;i++){
ptr=ptr->next;
}
for(i=0;i<=(last-n);i++){
printf("%d\n",ptr->info);
ptr=ptr->next;
}
}
void display(struct Node* head){
while(head!=NULL){
printf("Data:%d\n",head->info);
head=head->next;
}
}
void deleteDup(struct Node* head){
struct Node *ptr1,*ptr2,*temp;
ptr1=head;
while(ptr1!=NULL&&ptr1->next!=NULL){
ptr2=ptr1;
while(ptr2->next!=NULL){
if(ptr1->info==ptr2->next->info){
temp=ptr2->next;
ptr2->next=ptr2->next->next;
free(temp);
}
else{
ptr2=ptr2->next;
}
}
ptr1=ptr1->next;
}
}
void main(){
struct Node *head=NULL;
head=insert(head,10);
head=insert(head,20);
head=insert(head,30);
head=insert(head,10);
head=insert(head,10);
printf("BEFORE REVERSE\n");
display(head);
head=reverse(head);
printf("AFTER REVERSE\n");
display(head);
printf("NTH TO LAST\n");
nthlastElement(head,2);
//printf("AFTER DUPLICATE REMOVE\n");
//deleteDup(head);
//removeDuplicates(head);
//display(head);
}
Upvotes: 0
Reputation: 1416
Methods needed to run this program :
public static void main(String[] args) {
int iNoNodes = 10;
System.out.println("Total number of nodes : " + iNoNodes);
Node headNode = NodeUtils.createLinkedListOfNElements(iNoNodes);
Node ptrToSecondNode = headNode.getNext();
NodeUtils.printLinkedList(headNode);
reversePairInLinkedList(headNode);
NodeUtils.printLinkedList(ptrToSecondNode);
}
Approach is almost same, others are trying to explain. Code is self-explainatory.
private static void reversePairInLinkedList(Node headNode) {
Node tempNode = headNode;
if (tempNode == null || tempNode.getNext() == null)
return;
Node a = tempNode;
Node b = tempNode.getNext();
Node bNext = b.getNext(); //3
b.setNext(a);
if (bNext != null && bNext.getNext() != null)
a.setNext(bNext.getNext());
else
a.setNext(null);
reversePairInLinkedList(bNext);
}
Upvotes: 2
Reputation: 365
Simple recursive solution in Java:
public static void main(String[] args)
{
Node n = new Node(1);
n.next = new Node(2);
n.next.next = new Node(3);
n.next.next.next = new Node(4);
n.next.next.next.next = new Node(5);
n = swap(n);
}
public static Node swap(Node n)
{
if(n == null || n.next == null)
return n;
Node buffer = n;
n = n.next;
buffer.next = n.next;
n.next = buffer;
n.next.next = swap(buffer.next);
return n;
}
public static class Node
{
public int data; // value
public Node next; // pointer to next node
public Node(int value)
{
data = value;
}
}
Upvotes: 3
Reputation: 2079
Algo(node n1) -
keep 2 pointers n1 and n2, at the current 2 nodes. n1 --> n2 --->...
if(n1 and n2 link to each other) return n2;
if(n1 is NULL) return NULL;
if(n2 is NULL) return n1;
if(n1 and n2 do not link to each other and are not null)
change the pointer of n2 to n1.
call the algorthm recursively on n2.next
return n2;
Code (working) in c++
#include <iostream>
using namespace std;
class node
{
public:
int value;
node* next;
node(int val);
};
node::node(int val)
{
value = val;
}
node* reverse(node* n)
{
if(n==NULL) return NULL;
node* nxt = (*n).next;
if(nxt==NULL) return n;
if((*nxt).next==n) return nxt;
else
{
node* temp = (*nxt).next;
(*nxt).next = n;
(*n).next = reverse(temp);
}
return nxt;
}
void print(node* n)
{
node* temp = n;
while(temp!=NULL)
{
cout<<(*temp).value;
temp = (*temp).next;
}
cout << endl;
}
int main()
{
node* n = new node(0);
node* temp = n;
for(int i=1;i<10;i++)
{
node* n1 = new node(i);
(*temp).next = n1;
temp = n1;
}
print(n);
node* x = reverse(n);
print(x);
}
Upvotes: 1
Reputation: 86575
public static Node swapPairs(Node start)
{
// empty or one-node lists don't need swapping
if (start == null || start.next == start) return start;
// any list we return from here on will start at what's the second node atm
Node result = start.next;
Node current = start;
Node previous = null; // so we can fix links from the previous pair
do
{
Node node1 = current;
Node node2 = current.next;
// swap node1 and node2 (1->2->? ==> 2->1->?)
node1.next = node2.next;
node2.next = node1;
// If prev exists, it currently points at node1, not node2. Fix that
if (previous != null) previous.next = node2;
previous = current;
// only have to bump once more to get to the next pair;
// swapping already bumped us forward once
current = current.next;
} while (current != start && current.next != start);
// The tail needs to point at the new head
// (if current == start, then previous is the tail, otherwise current is)
((current == start) ? previous : current).next = result;
return result;
}
Upvotes: 0
Reputation: 6680
public static Node swapInPairs(Node n)
{
Node two;
if(n ==null ||n.next.next ==null)
{
Node one =n;
Node twoo = n.next;
twoo.next = one;
one.next =null;
return twoo;
}
else{
Node one = n;
two = n.next;
Node three = two.next;
two.next =one;
Node res = swapInPairs(three);
one.next =res;
}
return two;
}
I wrote the code at atomic level. So i hope it is self explanatory. I tested it. :)
Upvotes: 0
Reputation: 1349
public class Node
{
public int n; // value
public Node next; // pointer to next node
}
Node[] n = new Node[length];
for (int i=0; i<n.length; i++)
{
Node tmp = n[i];
n[i] = n[i+1];
n[i+1] = tmp;
n[i+1].next = n[i].next;
n[i].next = tmp;
}
Upvotes: -3
Reputation: 16047
I agree with @Stephen about not giving the answer (entirely), but I think I should give you hints.
An important thing to understand is that Java does not explicitly specify pointers - rather, whenever a non-primitive (e.g. not char, byte, int, double, float, long, boolean, short) is passed to a function, it is passed as a reference. So, you can use temporary variables to swap the values. Try to code one yourself or look below:
public static void swapNodeNexts(final Node n1, final Node n2) {
final Node n1Next = n1.next;
final Node n2Next = n2.next;
n2.next = n1Next;
n1.next = n2Next;
}
Then you'll need a data structure to hold the Nodes. It's important that there be an even number of Nodes only (odd numbers unnecessarily complicate things). It's also necessary to initialize the nodes. You should put this in your main method.
public static final int NUMPAIRS = 3;
public static void main(final String[] args) {
final Node[] nodeList = new Node[NUMPAIRS * 2];
for (int i = 0; i < nodeList.length; i++) {
nodeList[i] = new Node();
nodeList[i].n = (i + 1) * 10;
// 10 20 30 40
}
// ...
}
The important part is to set the Node next values. You can't just loop through with a for loop for all of them, because then the last one's next would throw an IndexOutOfBoundsException. Try to make one yourself, or peek at mine.
for (int i = 0; i < nodeList.length - 1; i++) {
nodeList[i].next = nodeList[i + 1];
}
nodeList[nodeList.length - 1].next = nodeList[0];
Then run your swap function on them with a for loop. But remember, you don't want to run it on every node… think about it a bit.
If you can't figure it out, here is my final code:
// Node
class Node {
public int n; // value
public Node next; // pointer to next node
@Override
public String toString() {
return "Node [n=" + n + ", nextValue=" + next.n + "]";
}
}
// NodeMain
public class NodeMain {
public static final int NUMPAIRS = 3;
public static void main(final String[] args) {
final Node[] nodeList = new Node[NUMPAIRS * 2];
for (int i = 0; i < nodeList.length; i++) {
nodeList[i] = new Node();
nodeList[i].n = (i + 1) * 10;
// 10 20 30 40
}
for (int i = 0; i < nodeList.length - 1; i++) {
nodeList[i].next = nodeList[i + 1];
}
nodeList[nodeList.length - 1].next = nodeList[0];
// This makes 1 -> 2 -> 3 -> 4 -> 1 etc.
printNodes(nodeList);
for (int i = 0; i < nodeList.length; i += 2) {
swapNodeNexts(nodeList[i], nodeList[i + 1]);
}
// Now: 2 -> 1 -> 4 -> 3 -> 1 etc.
printNodes(nodeList);
}
private static void printNodes(final Node[] nodeList) {
for (int i = 0; i < nodeList.length; i++) {
System.out.println("Node " + (i + 1) + ": " + nodeList[i].n
+ "; next: " + nodeList[i].next.n);
}
System.out.println();
}
private static void swapNodeNexts(final Node n1, final Node n2) {
final Node n1Next = n1.next;
final Node n2Next = n2.next;
n2.next = n1Next;
n1.next = n2Next;
}
}
I hope you were able to figure out at least some of this with guidance. More importantly, however, it's important that you understand the concepts here. If you have any questions, just leave a comment.
Upvotes: 3
Reputation: 47749
Yep, write an iterative routine that progresses two links in each iteration. Remember the link from the previous iteration so that you can back-patch it, then swap the current two links. The tricky parts are getting started (to a small extent) and knowing when to finish (to a larger one), especially if you end up having an odd number of elements.
Upvotes: 0
Reputation: 719446
The general approach to take is to step through the list, and on every other step you reorder the list nodes by assigning the node values.
But I think you will get more out of this (i.e. learn more) if you actually design, implement and test this yourself. (You don't get a free "phone a friend" or "ask SO" at a job interview ...)
Upvotes: 0