文章 220
评论 7
浏览 152707
LinkedList - 25. Reverse Nodes in k-Group

LinkedList - 25. Reverse Nodes in k-Group

  1. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

  • Only constant extra memory is allowed.
  • You may not alter the values in the list's nodes, only nodes itself may be changed.

思路:

题目意思是每k个节点翻转一次链表,如果节点不足k个,就不翻转,这是一个简单的实现题,运用递归的思想,找到翻转链表的起始点,然后翻转k个节点。难点就在于递归到终止条件,需要返回给上层调用栈的是已经反转的链表的head,作为上层反转的尾节点。然后就是简单的单链表翻转了。
所以可以先用一个计数器,来记录整个链表需要翻转的所有节点,把数据压入栈中,递归终止条件就只找到了链表尾,从最后一节k个节点,往上return进行翻转。

代码:

java:

/**

 * Definition for singly-linked list.

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        
        int count = 0;
        ListNode cur = head;
        while (cur != null && count != k) {
            cur = cur.next;
            count++;
        }
        
        if (count == k) {
            cur = reverseKGroup(cur, k);
            // resever list
            while (count-- > 0) {
                ListNode tmp = head.next;
                head.next = cur;
                cur = head;
                head = tmp;
            }
            head = cur;
        }
        
        return head;
    }
}

golang:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    // find k node from list
    var size int
    var cur = head
    for cur != nil && size < k {
        cur = cur.Next
        size++
    }
    
    
    // reverse list
    if size == k {
        cur = reverseKGroup(cur, k)
        for size > 0 {
            temp := head.Next
            head.Next = cur
            cur = head
            head = temp
            size--
        }
        head = cur
    }
    return head
}


标题:LinkedList - 25. Reverse Nodes in k-Group
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/07/27/1564237546279.html

Nothing just happens, it's all part of a plan.

取消