0

k个一组翻转链表

 3 months ago
source link: https://stellarx.github.io/post/5783bc85.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

花 风 城市

k个一组翻转链表

发表于2022-05-13|更新于2022-05-13|算法与数据结构
字数总计:134|阅读时长:1分钟|阅读量:2

递归:Java实现

  • 时间复杂度:O(2n) = O(n)
  • 空间复杂度:因为递归次数大概是n / k,所以O(n / k)
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null) return head;
ListNode tail = head;
for (int i = 0; i < k; i++) {
if (tail == null) return head;
tail = tail.next;
}
ListNode newHead = reverse(head, tail);
head.next = reverseKGroup(tail, k);
return newHead;
}
private ListNode reverse(ListNode head, ListNode tail) {
ListNode pre = null;
ListNode next = null;
while (head != tail) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK