61. Rotate List

61. Rotate List

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

Example:

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

思路： 把链表连成环，再在特定的位置断开。注意k可能大于链表的长度。

/** * 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 || k == 0) { return head; } int length = 1; ListNode node = head; while (node.next != null) { ++length; node = node.next; } node.next = head; int m = k % length; for (int i = 0; i < length - m; ++i) { node = node.next; } head = node.next; node.next = null; return head; }}

/** * 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 || k == 0) return head; int len = 1; ListNode node = head; while(node.next != null) { len++; node = node.next; } k = k % len; if (k == 0) return head; ListNode ptr = head; while(++k < len) ptr = ptr.next; ListNode ans = ptr.next; ptr.next = null; node.next = head; return ans; }}

/** * 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 = lengthOfList(head) for (let i = 0; i < (k % length); i++) { let newHead = new ListNode(), node = head, prev = head while (node.next) { prev = node node = node.next } if (length > 0) { prev.next = null newHead.val = node.val newHead.next = head head = newHead } } return head};const lengthOfList = head => { let node = head, length = 0 while (node) { node = node.next length++ } return length}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。