Rotate List (Java)

LeetCode

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Solution: when see  an ListNode question, recursion, two pointers  and link head and tail are always common ways to considered about.

In this question, link head and tail is a good choice. First, use an extra reference to go from head to tail meanwhile count the length of this list. once we got the length and the tail , we can do two things, one is linked the tail with head, another is calculate k depend on given n and the length of list, k is how many nodes should be move right. k=len-n%len; After we finished these two things, 

we can place an preHead reference at tail and let it go next k steps, then preHead will be the point just ahead our target head. then return break the list here and return our target head. 

	/*
	Given a list, rotate the list to the right by k places, where k is non-negative.
	For example:
	Given 1->2->3->4->5->NULL and k = 2,
	return 4->5->1->2->3->NULL.
	*/
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class RotateList {
	public ListNode rotateRight(ListNode head, int n) {
	if (head==null|| n==0){
	return head;
	}
	int len=1;
	ListNode last=head;
	// calculate the lenght of given list
	while(last.next!=null){
	last=last.next;
	len++;
	}
	last.next=head;
	// Should considered the situtation that n larger than given list's length
	int k=len-n%len;
	ListNode preHead=last;
	// find the point which are previuse for our target head
	while(k>0){
	preHead=preHead.next;
	k--;
	}
	head=preHead.next;
	preHead.next=null;
	return head;
	}
	}

view raw RotateList.java hosted with ❤ by GitHub

	/*
	Given a list, rotate the list to the right by k places, where k is non-negative.
	For example:
	Given 1->2->3->4->5->NULL and k = 2,
	return 4->5->1->2->3->NULL.
	*/
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class RotateList {
	public ListNode rotateRight(ListNode head, int n) {
	if (head==null|| n==0){
	return head;
	}
	int len=1;
	ListNode last=head;
	// calculate the lenght of given list
	while(last.next!=null){
	last=last.next;
	len++;
	}
	last.next=head;
	// Should considered the situtation that n larger than given list's length
	int k=len-n%len;
	ListNode preHead=last;
	// find the point which are previuse for our target head
	while(k>0){
	preHead=preHead.next;
	k--;
	}
	head=preHead.next;
	preHead.next=null;
	return head;
	}
	}

view raw RotateList.java hosted with ❤ by GitHub