leetcode 61. Rotate List
程序员文章站
2022-04-06 15:33:48
...
Rotate List算法思路:
首先,给链表加上一个虚拟头结点,利用双索引找到倒数第k+1个结点q和最后一个结点p,则q是转化后最后一个结点,q.next是转化后的第一个节点。利用穿针引线法将其重新连接成一个链表。最终返回的是q.next结点。考虑特殊情况,可以更好地优化算法,如果取余后k值为0或空链表,可直接返回head。
该算法时间复杂度O(n),空间复杂度O(1).。参考代码如下:
//leetcode 61. Rotate List
public static ListNode rotateRight(ListNode head, int k) {
ListNode vmNode = new ListNode(0);
vmNode.next = head;
ListNode p = head,q = vmNode,pre=vmNode;
int n=0;
while(p!=null){
++n;
p = p.next;
}
if(n!=0)
k = k%n;
if(k==0)
return head;
p = vmNode;
while((k+1)!=0&&p!=null){
pre = p;
p = p.next;
--k;
}
while(p!=null&&q!=null){
q = q.next;
pre = p;
p = p.next;
}
ListNode head_q = q.next;
q.next = null;
pre.next=head;
return head_q;
}
找到倒数第k个结点并删除该结点的算法:
//leetcode 19. Remove Nth Node From End of List
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode vmNode = new ListNode(0);
vmNode.next = head;
ListNode p = vmNode,q=vmNode;
while((n+1) !=0&&p!=null){
p = p.next;
n--;
}
while(p!=null){
q = q.next;
p = p.next;
}
q.next = q.next.next;
return vmNode.next;
}
推荐阅读
-
Leetcode0143--Reorder List 链表重排
-
【LeetCode OJ 328】Odd Even Linked List
-
leetcode 328. Odd Even Linked List
-
leetcode 328. Odd Even Linked List
-
【Leetcode】328.(Medium)Odd Even Linked List
-
LeetCode 83. Remove Duplicates from Sorted List
-
LeetCode 83. Remove Duplicates from Sorted List
-
LeetCode 83. Remove Duplicates from Sorted List ***
-
Leetcode 83. Remove Duplicates from Sorted List
-
[Leetcode] 142. Linked List Cycle II (set / 快慢指针)