Singly linked list in java

Question

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?

Answer 1

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.

Answer 2

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;
    }
}

Answer 3

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);
}

Answer 4

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);

}