Copy the last num nodes of a given linked list starting from head and create a n
ID: 3562960 • Letter: C
Question
Copy the last num nodes of a given linked list starting from head and create a new linked list with the values in these nodes. The copy should not affect the original linked list.
The pre-condition is that num is non-negative.
When num is bigger than the number of nodes in the list, it should copy the entire linked list.
This method should return the linked list with the new head.
NOTE: The elements in the list starting from head do not need to be ordered.
For example, given a list with the head pointing to the node with value 0.
copyLast(head, 1) should return a new linked list
copyLast(head, 2) should return a new linked list
copyLast(head, 7) should return a new linked list
I have basic methods:
private int data; // declare instance variables
private IntNode link;
public IntNode() { // default no argument constructor
data = 0;
link = null;
}
public IntNode(int intdata, IntNode intlink) { // create IntNode method with two arguments for data and link elements
data = intdata;
link = intlink;
}
public int getData(){ // get method to get node value
return data;
}
public IntNode getLink(){ // get method to get link value
return link;
}
public void setData(int _d){ // set method to set node value
data = _d;
}
public void setLink(IntNode _l){ // set method to set node link
link = _l;
}
Explanation / Answer
private int data; // declare instance variables
private IntNode link;
public IntNode() { // default no argument constructor
data = 0;
link = null;
}
public IntNode(int intdata, IntNode intlink) { // create IntNode method with two arguments for data and link elements
data = intdata;
link = intlink;
}
public int getData(){ // get method to get node value
return data;
}
public IntNode getLink(){ // get method to get link value
return link;
}
public void setData(int _d){ // set method to set node value
data = _d;
}
public void setLink(IntNode _l){ // set method to set node link
link = _l;
}
private IntNode getLastN(IntNode head, int n){
//Assuming that head is the head of original list
IntNode temp = head,temp2=head,last;
boolean flag = false;
int i;
for(i=0;temp != null;i++,m++,temp=temp.link){
if(i == n-1){//Start pointing to start once n nodes have been traversed
temp2 = head;
flag = true;
continue;
}
if(flag){//Move to next node until end of list is reached
temp2 = temp2.link;
}
}
//in the end, temp2 will point to nth node from last
//If i < n, then temp2 will keep on pointing to head of original list
//due to initialization of temp2.
//Now create a new linked list with this head
IntNode head2 = new IntNode(temp2.data,null);
last = head2;
temp2 = temp2.link;
while(temp2 != null){
//Copy data from original list node to new node
temp = new Node(temp2.data,null);
//Link this new node to last node
last.link = temp;
//Make this the new last node
last = temp;
//Move to next node in original list
temp2 = temp2.link;
}
//Return head of new list
return head2;
}