单链表旋转
geosmart opened this issue · 0 comments
geosmart commented
给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
算法步骤
旋转链表
- 求链表长度
- 计算实际需要移动的位置k
- 快慢指针法找到倒数第k个节点
- 链表旋转:k节点作为新的链表头,k-1节点作为链表尾,中间部分以循环链表方式连接
复杂度
- 空间复杂度:O(1)
- 时间复杂度:O(n)
代码实现
版本1
public static ListNode rotateRight(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode tmp = dummy.next;
int n = 0;
//求链表长度
while (tmp != null) {
tmp = tmp.next;
n++;
}
if (n == 0 || k % n == 0) {
return dummy.next;
}
//当成循环链表,n次移动等于没移动,求余后的k为实际需移动的位置数
k = k % n;
//快慢指针求倒数第k个节点
ListNode slow = dummy;
ListNode fast = dummy;
while (k > 0) {
fast = fast.next;
k--;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
//kNode为返回结果的head
ListNode kNode = slow.next;
//原slow节点即为tail
slow.next = null;
//连接原链表的头部
fast.next = head;
return kNode;
}
版本2:快慢指针法,关键是k = k % n
public static ListNode rotateRight(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy.next;
int n = 1;
//快指针,求链表长度和tail节点
while (fast.next != null) {
fast = fast.next;
n++;
}
//n次移动等于没移动
if (k % n == 0) {
return dummy.next;
}
//当成循环链表,求余后的k为实际需移动的位置数
k = k % n;
ListNode slow = dummy.next;
//求倒数第k个节点
for (int i = 0; i < n - k - 1; i++) {
slow = slow.next;
}
ListNode newHead = slow.next;
slow.next = null;
//连接原链表的头部
fast.next = head;
return newHead;
}