61.rotate-list.md

旋转链表

题目

思路1

链表右移动. 只需要找到最后一个节点, 将该节点指向第一个节点, 同时将上一个节点指向移除即可.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
  if (!head) {
    return head
  }
  let i = 0
  while (i < k) {
    head = rotate(head)
    i++
  }
  return head
};

function rotate (head) {
  if (!head.next) {
    return head
  }
  let curr = head
  let prev = head
  while (curr.next) {
    prev = curr
    curr = curr.next
    if (!curr.next) {
      prev.next = null
      curr.next = head
      return curr
    }
  }
}

优化: 减少重复移动.

如果整个链表长度只有5, 而循环次数超过5次的话, 那么就会有5次移动其实是无用功的.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
  if (!head) {
    return head
  }
  const length = getLisNodeLength(head)

  k = length < k ? k % length : k
  console.log(k, length)
  let i = 0
  while (i < k) {
    head = rotate(head)
    i++
  }
  return head
};

function rotate (head) {
  if (!head.next) {
    return head
  }
  let curr = head
  let prev = head
  while (curr.next) {
    prev = curr
    curr = curr.next
    if (!curr.next) {
      prev.next = null
      curr.next = head
      return curr
    }
  }
}

function getLisNodeLength (head) {
  let count = 0
  while (head.next) {
    head = head.next
    count++
  }
  return count + 1
}

再仔细观察一下题目, 发现其实整个最多只用做两件事:

1. 最终的head链表要与之前的上一个链表断开.
2. 原先的head要与最后一位连接上即可.

head
1	2	3	4	5
右移2位
			head		head要往左边移动两位
1	2	3	4	5	1与5连接, 3与4断开, 返回4即可

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
  if (!head || !head.next) {
    return head
  }
  const arr = []
  while (head) {
    arr.push(head)
    head = head.next
  }
  const length = arr.length
  k = length <= k ? k % length : k
  if (k > 0) {
    arr[length - 1].next = arr[0]
    arr[length - k - 1].next = null
    return arr[length - k]
  }
  return arr[0]
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null) {
      return head;
    }
    ArrayList<ListNode> arr = new ArrayList<ListNode>();
    while (head != null) {
      arr.add(head);
      head = head.next;
    }
    int length = arr.size();
    k = length <= k ? k % length : k;
    if (k > 0) {
      arr.get(length - 1).next = arr.get(0);
      arr.get(length - 1 - k).next = null;
      return arr.get(length - k);
    }
    return arr.get(0);
  }
}