给一个单向链表以及整数N,使得每N个元素为一组进行翻转。要求时间复杂度O(n), 空间复杂度O(1)。
/* 迭代版本, 维护两个指针, 分别指向待反转了的head和tail. */ import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * reverse the given linked list * @param head ListNode类 the head of the linked list * @param n int整型 the N * @return ListNode类 */ public ListNode reverseLinkedList (ListNode head, int n) { // write code here if(head == null) return null; if(head.next == null || n <= 1) return head; ListNode nHead = head, nTail = head; ListNode prev = null; boolean flag = true; while(nHead != null){ int t = 1; while(t < n && nTail.next != null){ nHead = insertInHead(prev, nHead, nTail); t ++; } if(flag){ flag = false; head = nHead; } nHead = nTail.next; prev = nTail; nTail = nHead; } return head; } static ListNode insertInHead(ListNode prev, ListNode head, ListNode tail){ if(tail == null) return head; if(head == null) return null; ListNode next = tail.next; tail.next = next.next; next.next = head; if(prev != null){ prev.next = next; } return next; } }
public class Solution { /** * reverse the given linked list * @param head ListNode类 the head of the linked list * @param n int整型 the N * @return ListNode类 */ public ListNode reverseLinkedList (ListNode head, int n) { if(head == null) return null; ListNode a = head; ListNode b = head; for(int i = 0; i < n; i++){ if(b == null) break; b = b.next; } ListNode newHead = newReverse(a,b); a.next = reverseLinkedList(b,n); return newHead; } //可以参考LeetCOde反转链表,多一个条件:当前节点不为尾节点b public ListNode newReverse(ListNode a, ListNode b){ ListNode pre = null; ListNode cur = a; while(cur != null && cur != b){ ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { public ListNode reverseLinkedList (ListNode head, int n) { if (n == 1) { //保证翻转1个以上 return head; } ListNode res = new ListNode(0), result = res; res.next = head; ListNode pre, post; while (head != null) { pre = findNextHead(head, n); post = pre.next; pre.next = null; //翻转当前这段 pre = reverse(head); res.next = pre; head.next = post; res = head; head = head.next; } return result.next; } //翻转链表 private ListNode reverse(ListNode head) { ListNode pre = null, post = head; while (post != null) { ListNode tmp = post.next; post.next = pre; pre = post; post = tmp; } return pre; } //找到下一截翻转起点 //并与前一段切断 private ListNode findNextHead(ListNode head, int k) { ListNode pre = null; while (head != null && k > 0) { pre = head; head = head.next; k--; } return pre; } }
这道题其实不难,只是开始时,要反转两个链表,后面每次循环反转一个链表,为了屏蔽差异,引入头节点,这是链表操作常用的技巧。 public ListNode reverseLinkedList(ListNode head, int n) { // write code here ListNode start = new ListNode(0); ListNode cur; ListNode next; ListNode pre = null; ListNode tail = start; cur = head; int count = 0; while (cur != null) { ListNode tmp = cur; count = 0; while (cur != null && count < n) { next = cur.next; cur.next = pre; pre = cur; cur = next; count++; } tail.next = pre; tail = tmp; pre = null; } return start.next; }
class Solution: def reverseLinkedList(self , head , n ): if not head: return if not head.next&nbs***bsp;n == 1: return head # 标记是否为第一组,需要确定新的head flag = True res_head = head tail = head while head: # 先判断是否还剩下一组k个结点的链表 test = head # 记录剩余不足k个结点的链表长度 last = 0 for i in range(n): if not test: break last += 1 test = test.next # 直接翻转后面剩余结点的个数 cnt = last - 1 cur_head = head while cnt: cnt -= 1 new_head = head.next head.next = head.next.next new_head.next = cur_head cur_head = new_head # 第一组之后的每一组都要更新上一组的末尾结点指向当前这一组的cur_head if not flag: tail.next = cur_head else: # 如果这是第一组,更新并记录新的res_head res_head = cur_head flag = False # 这一组的末尾结点就是当前的head tail = head # 进入下一组的翻转 head = head.next return res_head
class Solution { public: /** * reverse the given linked list * @param head ListNode类 the head of the linked list * @param n int整型 the N * @return ListNode类 */ ListNode* reverseLinkedList(ListNode* head, int n) { // write code here ListNode* tmp = head; ListNode* next_ = new ListNode(0); ListNode* prev = nullptr; ListNode* node = new ListNode(0); queue<ListNode*> q; while (tmp) { node = tmp; for (int i = 0; i < n && tmp != nullptr; i++) { next_ = tmp->next; tmp->next = prev; prev = tmp; tmp = next_; } q.push(prev); q.push(node); prev = nullptr; } ListNode* ans = q.front(); while (!q.empty()) { q.pop(); ListNode* a = q.front(); q.pop(); a->next = q.front(); } return ans; } };
本题是LeetCode 25. Reverse Nodes in k-Group的简化版本(反转前无需判断最后是否剩余K个节点)
用递归的方法来解相对好记, 但会占用更多内存
具体解法如下
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: ListNode* reverseLinkedList(ListNode* head, int n) { // 一个链表头部增加/减少 n 个元素后适用同样的方法 // 给出终止条件 1. 空链表 2. 仅有头部节点 3. 组内元素个数小于1(无需翻转) if (head == nullptr || head->next == nullptr || n<=1){ return head; } ListNode *pit = head, *it = head->next, *nit; int step = n-1; // it 从第二个节点开始 // 逐个翻转结点 while (step && it != nullptr){ nit = it->next; it->next = pit; pit = it; it = nit; --step; } // 终止时 it 经过 n 个节点 恰好为下一组的起点 // head 成为新的尾部连接翻转后的头部 // pit 成为新的头部直接返回 head->next = reverseLinkedList(it, n); return pit; } };
总体时间复杂度 O(N), 空间复杂度 O(1)
本题运行时间: 8 ms 占用内存:536K
/* 1. 特判head为空和n=1的情况 2. 记录上一组翻转后的尾部lastTail和当前组翻转后的头部nowHead和尾部nowTail,当组数>=2时,将lastTail和nowHead链接 3. head标记链接对<head, p>中的前一个元素,p->next=head */ ListNode* reverseLinkedList(ListNode* head, int n) { ListNode *p, *nowTail, *p_next, *nowHead, *lastTail, *ans; bool f = false; if(head==NULL || n==1 ) return head; while(1) { int cnt = 0; p = head->next; nowHead = nowTail = head; //翻转前的起始位置是翻转后的尾 // head p p_next 链接对<head, p>, // 1 2 3 // 2 3 4 while(p!=NULL) { p_next = p->next; p->next = head; // head<-p cnt++; nowHead = head = p; p = p_next; if(cnt==n-1) { head = p_next; // 此段结束,下一段的第一个链接对 break; } } if(f) lastTail->next = nowHead; // 段数>=2时,段和段之间进行链接 if(!f) { f = true; ans = nowHead; // 翻转后的头部是第一段的头部 } lastTail = nowTail; // 翻转之后当前段的尾,即将于下一段翻转后的头相连 if(p==NULL) { nowTail->next = NULL; //结束前将尾部的next置为NULL break; } } return ans; }
没有特判传入的链表为空的情况,段错误了好久了QAQ
class Solution: def reverseLinkedList(self , head , n ): i,j=0,0 pre=None cur=head t0=head while cur: temp=cur.next if n==1: return head if i==0: t=cur if i==n-1: cur.next=pre if j==0: newh=cur j=1 else: t0.next=cur t0=t pre=None cur=temp i=0 continue cur.next=pre pre=cur cur=temp i+=1 if j==0: newh=pre elif i!=0: t0.next=pre return newh
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * reverse the given linked list * @param head ListNode类 the head of the linked list * @param n int整型 the N * @return ListNode类 */ ListNode* reverseLinkedList(ListNode* head, int n) { // write code here if(n <= 1) return head; ListNode* tmp = head; ListNode* pre = head; for(int i = 0; i < n; i++){ if(tmp == nullptr) break; tmp = tmp->next; } ListNode* newHead = reverse(head, tmp); head->next = reverseLinkedList(tmp, n); return newHead; } ListNode* reverse(ListNode* a, ListNode* b) { ListNode* pre, *cur, *next; pre = nullptr; cur = a; next = b; while(cur != nullptr && cur != b) { next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } };
class Solution { public: /** * reverse the given linked list * @param head ListNode类 the head of the linked list * @param n int整型 the N * @return ListNode类 */ ListNode* reverseLinkedList(ListNode* head, int n) { // write code here if(n <= 1) return head; ListNode* tmp = head; ListNode* pre = head; int len = 1; for(int i = 0; i < n; i++){ if(tmp == nullptr) break; tmp = tmp->next; len++; } auto reverse = [](ListNode* a, ListNode* b) -> ListNode* { ListNode* pre, *cur, *next; pre = nullptr; cur = a; next = b; while(cur != nullptr && cur != b) { next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; }; ListNode* newHead = reverse(head, tmp); if(len <= n) { //如果长度<=n只需要反转一次 return newHead; } //题目不让递归,那就迭代咯 ListNode* curTail = head; //迭代时,记录每次反转后的尾节点 while(tmp != nullptr) { // 用于连接下一个反转子链表的头节点 head = tmp; for(int i = 0; i < n; i++) { if(tmp == nullptr) break; tmp = tmp->next; } curTail->next = reverse(head, tmp); curTail = head; } return newHead; } };
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * reverse the given linked list * @param head ListNode类 the head of the linked list * @param n int整型 the N * @return ListNode类 */ public ListNode reverseLinkedList (ListNode head, int n) { // write code here if (n <= 1) { return head; } // write code here ListNode newHead = new ListNode(-1); newHead.next = head; ListNode p = newHead, q, post, rear; while (p.next != null) { q = p.next; rear = p.next; p.next = null; int k = 0; while (q != null && k < n) { post = q.next; q.next = p.next; p.next = q; q = post; ++k; } rear.next = q; p = rear; } return newHead.next; } }
class Solution { public: ListNode* reverseLinkedList(ListNode* head, int n) { if (!head || !head->next) { return head; } int len = 0; ListNode* p = head; while (p) { ++len; p = p->next; } int loop = len / n; if (len % n) { loop++; } ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* pre = dummy; p = head; ListNode* pnext = p->next; while (loop--) { //p->next = NULL; if (!loop) { n = (len % n) ? len % n : n; } for (int i = 0; i < n - 1; ++i) { ListNode* tmp = pnext->next; pnext->next = pre->next; pre->next = pnext; pnext = tmp; } pre = p; p->next = pnext; p = pnext; if (!pnext) { break; } pnext = pnext->next; } head = dummy->next; delete dummy; return head; } };