LeetCode -- Rotate List

LeetCode -- Rotate List

題目描述：


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.


就是將倒數K個節點放在鏈表前。


思路：
1. 遍歷鏈表判斷長度len是否小於k，如果是，則k = k % len
2. 如果len = k或len < 2或k < 1，直接返回
3. 遍歷鏈表，移動len - k - 1個位置，存當前位置為q
4. 將q之後的節點存入stack
5. 遍歷stack，依次將節點設為頭結點
6. 最後，將q.next指向Null


實現代碼：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode RotateRight(ListNode head, int k) 
    {
        if(head == null){
    		return null;
    	}
        var len = LenOf(head);
    	if(len < 2 || k == len || k < 1){
    		return head;
    	}
    	if(k > len){
    		k = k % len;
    	}
    	
    	var stack = new Stack();
    	var p = head;
    	
    	for(var i = 0;i < len - k - 1;i ++){
    		p = p.next;
    	}
    	
    	var q = p;
    	
    	p = p.next;
    	while(p != null){
    		stack.Push(p.val);
    		p = p.next;
    	}
    	q.next = null;
    	
    	while(stack.Count > 0)
    	{
    		var n = new ListNode(stack.Pop());
    		n.next = head;
    		head = n;
    	}
    	
    	return head;
    }


private int LenOf(ListNode head)
{
	var p = head;
	var len = 0;
	while(p != null){
		len ++;
		p = p.next;
	}
	return len;
}
}