- 设计思想:
-视频讲解链接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 };