/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package LinkedList;
/**
*
* @author shayzukerman
*/
public class MyLinkedList
{
private Node head;
private Node tail;
private int nodeCnt;
public MyLinkedList()
{
this.head = this.tail = null;
this.nodeCnt = 0;
}
public MyLinkedList(int[] inpArr)
{
this();
for (int val : inpArr)
this.addNode(val);
}
/**
* Add new element to the List
* @param value - Node's value
*/
public void addNode(int value)
{
Node newNode = new Node(value);
if (head == null)
head = newNode;
else
tail.setNext(newNode);
tail = newNode;
nodeCnt++;
}
public void swapList()
{
swapListRec(head, null);
// Node prev = null,
// curr,
// next;
//
// curr = tail = head;
// while (curr != null)
// {
// next = curr.getNext();
// curr.setNext(prev);
// prev = curr;
// curr = next;
// }
// head = prev;
}
public void swapListRec(Node curr, Node prev)
{
Node next = curr.getNext();
if (next == null)
{
tail = head;
head = curr;
}
else
swapListRec(next, curr);
curr.setNext(prev);
}
public void reorderList()
{
Node ptrHead1 = null, ptrTai11 = null,
ptrHead2 = null, ptrTail2 = null;
Node curr1, curr2;
Node ptr = head;
curr2 = null;
if (head == null)
return;
boolean add2ptr1 = true;
while (ptr != null)
{
Node next = ptr.getNext();
if (add2ptr1)
{
if (ptrHead1 == null)
ptrHead1 = ptr;
else
ptrTai11.setNext(ptr);
ptrTai11 = ptr;
// Since we don't know if we reach here at the end of the
// scan, always assign null at the end of the list:
ptrTai11.setNext(null);
add2ptr1 = false;
}
else
{
if (ptrTail2 == null)
ptrTail2 = ptr;
ptr.setNext(curr2);
// Since we don't know if we reach here at the end of the
// scan, always assign the current node to head:
ptrHead2 = ptr;
curr2 = ptr;
add2ptr1 = true;
}
ptr = next;
}
System.
out.
println("List1: " + linkedList2Str
(ptrHead1
)); System.
out.
println("List2: " + linkedList2Str
(ptrHead2
));
Node newHead = null;
Node newTail = null;
curr1 = ptrHead1;
curr2 = ptrHead2;
add2ptr1 = true;
while (curr1 != null || curr2 != null)
{
ptr = (add2ptr1) ? curr1 : curr2;
if (ptr != null)
{
if (newHead == null)
newHead = ptr;
else
newTail.setNext(ptr);
newTail = ptr;
}
if (add2ptr1)
{
curr1 = curr1.getNext();
if (curr2 != null)
add2ptr1 = false;
}
else
{
curr2 = curr2.getNext();
if (curr1 != null)
add2ptr1 = true;
}
}
head = newHead;
tail = newTail;
}
@Override
{
return (linkedList2Str(this.head));
}
public String linkedList2Str
(Node head
) {
if (head == null)
return ("{enpty}");
StringBuilder retStb = new StringBuilder();
for (Node ptr = head; ptr != null; ptr = ptr.getNext())
retStb.append(ptr);
return("{ " + retStb.toString() + " }");
}
public static void main
(String[] args
) {
int[] inpArr = {1, 2, 3, 4};
//int[] inpArr = {1, 2, 3};
MyLinkedList myList = new MyLinkedList(inpArr);
System.
out.
println("My List: " + myList
);
myList.reorderList();
System.
out.
println("My List: " + myList
); myList.swapList();
System.
out.
println("My List: " + myList
); // myList.addNode(1);
// System.out.println("My List: " + myList);
// myList.swapList();
// System.out.println("My List: " + myList);
}
}
Loading...