Created
February 19, 2020 02:01
-
-
Save yeshvantbhavnasi/ffd3729a13757d43e6774d628886cf56 to your computer and use it in GitHub Desktop.
Linked List methods
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.List; | |
class Test { | |
static class ListNode { | |
int data; | |
ListNode next; | |
public ListNode(int data) { | |
this.data = data; | |
} | |
public String toString() { | |
return this.data+""; | |
} | |
} | |
public static void main(String[] args) | |
{ | |
ListNode n1 = new ListNode(1); | |
ListNode n2 = new ListNode(2); | |
n1.next = n2; | |
ListNode n3 = new ListNode(3); | |
n2.next = n3; | |
ListNode n4 = new ListNode(4); | |
n3.next = n4; | |
ListNode n5 = new ListNode(5); | |
n4.next = n5; | |
//ListNode rotated = rotate(n1); | |
reverseN(n1,3); | |
} | |
public static ListNode reverseN(ListNode head, int n) { | |
ListNode prev = null, next = null; | |
List<ListNode> lists = new ArrayList<>(); | |
int counter = 0; | |
ListNode curr = head; | |
ListNode lastHead = null; | |
while(curr != null) { | |
if(counter == n) { | |
if(lastHead != null) { | |
lastHead.next = prev; | |
} | |
lastHead = head; | |
head = curr; | |
lists.add(prev); | |
prev = null; | |
counter = 0; | |
} | |
next = curr.next; | |
curr.next = prev; | |
prev = curr; | |
curr = next; | |
counter++; | |
} | |
if(counter > 0) { | |
lists.add(prev); | |
lastHead.next = prev; | |
} | |
System.out.println(lists); | |
printNode(lists.get(0)); | |
return null; | |
} | |
public static ListNode rotate(ListNode head) { | |
ListNode node = head; | |
ListNode center = findCenter(node); | |
ListNode secondHalf = reverse(center); | |
printNode(secondHalf); | |
printNode(head); | |
ListNode ret = new ListNode(-1); | |
ListNode curr = ret; | |
int i = 0; | |
while(head != null) { | |
if(i%2 == 0) { | |
curr.next = head; | |
head = head.next; | |
} else { | |
curr.next = secondHalf; | |
secondHalf = secondHalf.next; | |
} | |
i++; | |
curr = curr.next; | |
} | |
printNode(ret.next); | |
return ret.next; | |
} | |
private static ListNode reverse(ListNode head) { | |
ListNode curr = head; | |
ListNode prev = null, next = null; | |
while (curr != null) { | |
next = curr.next; | |
curr.next = prev; | |
prev = curr; | |
curr = next; | |
} | |
return prev; | |
} | |
private static ListNode findCenter(ListNode head) { | |
ListNode fp = head; | |
ListNode sp = head; | |
while (fp != null) { | |
fp = fp.next; | |
if(fp != null && fp.next != null) { | |
fp = fp.next; | |
sp = sp.next; | |
} | |
} | |
return sp; | |
} | |
private static void printNode(ListNode head) { | |
while (head != null) { | |
System.out.print(head.data); | |
head = head.next; | |
} | |
System.out.println(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment