[C++] 「LeetCode」61. 旋转链表

• 旋转链表
  给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
  
  

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   int val;
 *   ListNode next;
 *   ListNode() {}
 *   ListNode(int val) { this.val = val; }
 *   ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode rotateRight(ListNode head, int k) {
      if (head == null || head.next == null)return head;
       
      int len =1;
      ListNode  oldTail = head;
      while (oldTail.next!=null) {
        oldTail = oldTail.next;
        len++;
      }
      oldTail.next = head;
      ListNode newTail = head;
      for(int i =0; i < len - k% len -1; i++){
        newTail = newTail.next;
      }
      ListNode newHead = newTail.next;
      newTail.next =null;
      return newHead;
  }
}

class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    // 1. 特判
    if(k == 0 || head == null || head.next == null){
      return head;
    }
    // 2. 计算出原链表的长度为n
    int n = 1;
    ListNode iter = head;
    while(iter.next != null){
      iter = iter.next;
      n++;                // 此时n记录的是链表的末尾节点
    }
    // 3. 找到移动k位后新链表的最后一个节点
    int add = n - k % n;          // add 记录的是新链表的最后一个节点
    if(add == n){               // 如果k 刚好为n的整数倍数，新链表将于原链表相同
      return head;            // 直接返回原链表即可
    }
    // 4. 处理逻辑
    iter.next = head;             // 将当前链表闭合为环
    while(add-- > 0){             // 将iter指向新链表的最后一个节点位置
      iter = iter.next;   
    }
    ListNode ret = iter.next;         // 此时 ret为移动k位后新链表的头
    iter.next = null;             // 将环断开
    return ret;               // 返回新链表
  }
}