NC50 链表中的节点每k个一组翻转（四种语言+代码）

- 题目描述：

- 题目链接：
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=188&&tqId=38557&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking

- 设计思想：

-视频讲解链接B站视频讲解
- 复杂度分析：

- 代码：
c++版本:

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */

    pair<ListNode*, ListNode*> reverseList(ListNode* head, ListNode* temp) {
        //head代表翻转的头，temp代表尾巴
        ListNode* pre = temp->next;//保存尾巴的下一个节点信息
        ListNode* res = nullptr;//开辟一个新的链表
        ListNode* cur = head;//用来遍历链表head
        while (cur != pre) {
            ListNode* Temp = cur->next;
            cur->next = res;
            res = cur;
            cur = Temp;
        }
        return {temp, head};
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if(head == nullptr || head->next == nullptr || k == 1) return head;//特殊情况
        ListNode* res = new ListNode(-1);
        res->next = head;
        ListNode* cur = res;
        while(cur != nullptr){
            ListNode* temp = cur;
            for(int i = 0;i < k;i ++){
                temp = temp->next;
                if(temp == nullptr) return res->next;//如果走到了最后直接返回，不需要后续操作
            }
            ListNode* nxt = temp->next;//因为每一组要反转，需要保存翻转前的下一个节点
            pair<ListNode*, ListNode*>reverse = reverseList(head,temp);
            head = reverse.first;
            temp = reverse.second;
            //把翻转部分的链表重新接到原链表上
            cur->next = head;
            temp->next = nxt;
            cur = temp;
            head = temp->next;
        }
        return res->next;
    }
};

Java版本：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if(head==null||head.next==null||k==1) return head;//特殊情况
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode cur = res;
        while(head != null){
            ListNode temp = cur;
            ///查看剩余部分的长度是否大于K
            for(int i = 0;i < k;i ++){
                temp = temp.next;
                if(temp == null) return res.next;//如果走到了最后直接返回，不需要后续操作
            }
            ListNode nxt = temp.next;///因为每一组要反转，需要保存翻转前的下一个节点
            ListNode []reverse = reverseList(head,temp);
            head = reverse[0];
            temp = reverse[1];
            cur.next = head;
           // head.next = temp;
            temp.next = nxt;
            cur = temp;
            head = temp.next;

        }
        return res.next;
    }
    public ListNode[] reverseList(ListNode head, ListNode temp) {
        ListNode pre = temp.next;
        ListNode res = null;
        ListNode cur = head;
        while(cur != pre){
            ListNode Temp = cur.next;
            cur.next = res;
            res = cur;
            cur =Temp;
       }
        return new ListNode[]{temp, head};
    }
}

Python版本:

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    def reverseList(self,head,temp):
        #翻转链表
        pre = temp.next
        res = None
        cur = head
        while cur != pre:
            Temp = cur.next
            cur.next = res
            res = cur
            cur = Temp
        return temp,head

    def reverseKGroup(self , head , k ):
        # write code here
        if head == None or head.next == None or k == 1: return head#特殊情况
        res = ListNode(-1)
        res.next = head
        cur = res
        while head:
            #查看剩余部分的长度是否大于K
            temp = cur
            for i in range(k):
                temp = temp.next
                if temp == None:return res.next#如果走到了最后直接返回，不需要后续操作
            nxt = temp.next#因为每一组要反转，需要保存翻转前的下一个节点
            head,temp = self.reverseList(head,temp)
            #把翻转部分的链表重新接到原链表上
            cur.next = head
            temp.next = nxt
            cur = temp
            head = temp.next
        return res.next;

JavaScript版本:

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param k int整型 
  * @return ListNode类
  */
function reverseList( head ,temp) {
        //翻转链表
        let pre = temp.next;
        let res = null;
        let cur = head;
        while(cur != pre){
            let Temp = cur.next;
            cur.next = res;
            res = cur;
            cur =Temp;
       }
        return [temp, head];    
}  
function reverseKGroup( head ,  k ) {
    // write code here
    if(head==null||head.next==null||k==1) return head;//特殊情况
        let res = new ListNode(-1);
        res.next = head;
        let cur = res;
        while(head != null){
            let temp = cur;
            //查看剩余部分的长度是否大于K
            for(let i = 0;i < k;i ++){
                temp = temp.next;
                if(temp == null) return res.next;//如果走到了最后直接返回，不需要后续操作
            }
            let nxt = temp.next;//因为每一组要反转，需要保存翻转前的下一个节点
            [head, temp] = reverseList(head,temp);
            //把翻转部分的链表重新接到原链表上
            cur.next = head;
           // head.next = temp;
            temp.next = nxt;
            cur = temp;
            head = temp.next;

        }
        return res.next;
}
module.exports = {
    reverseKGroup : reverseKGroup
};