思想:
把原始链表节点一个个切下来，粘到左边的新链表上（左链表初始为空)
时间复杂度O(n),空间复杂度O(1)
链表变化过程:
node1->node2->node3-node4
一个个切下粘到左边
node1 … node2->node3->node4
node1<-node2 …. node3->node4
node1<-node2<-node3 …. node4
node1<-node2<-node3<-node4
代码思路: 循环切下每个节点,依次粘到左侧链表中
1. 保存当前被切节点的next, 即切后原始链表的头结点,(4)里迭代下一个节点要用
2. 切下的节点粘贴到左边
3. 左边链表增加节点后更新头结点
4. 迭代下一个被切的节点, 即原始链表的头结点
(1)中保存next目的是为了(4)中用,如果不保存,经过二操作后cur->next节点就不是原来cur->next节点了)
递归版中3和4步和在一起了,
链表定义
|
|
struct node{ int value; node* next; }; |
循环版本代码
|
|
struct node* reverseList(struct node* head) { struct node* leftList = NULL;//（左链表初始为空） struct node* curNode = head; //链表要切下的第一个节点 while (curNode) { head = curNode->next;// 1. cur被切下后,cur->next变成原始链表的新头结点,需要保存 curNode->next = leftList;// 2. 被切下的节点指向左边新链表,即粘到左边的链表上 leftList = curNode; // 2. 左边的新链表加入一个节点后,需要更新头结点 curNode = head;// 4. 迭代下一个被切的节点,即现在原始链表的头结点(被之前保存下来的) } return leftList; } |
递归版
采用尾递归,翻转完成时候直接返回左边链表即可
|
|
// left为上文提到的左边的链表,传入NULL即可,cur需要翻转的链表头结点 node* reverseList(struct node* left, node* cur){ if(cur == NULL) return left; node * oldHead = cur-> next;//1. 保存当前被切节点的下一个节点,即被切后原始链表的头结点 cur->next = left; // 2. 切下来的节点粘到左边 return reverseList(cur, oldHead); //3和4向右递归即可, cur为左边链表头结点, oldHead为下一个要切的节点,即原始链表的头结点 } |
每k个节点翻转
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
node *res = new node(); node *left = res; node *p = p1; int k = 2; while (p) { int kt = k - 1; node *head = p; while (kt-- && head) { head = head->next; } if (head) { node *newhead = head->next; head->next = NULL; head = reverse(NULL, p); p = newhead; } else { head = reverse(NULL, p); p = NULL; } while (left->next) { left = left->next; } left->next = head; } res = res->next; while (res) { cout << res->value << " "; res = res->next; } |
翻转链表尾插法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
node *merge(node *p1, node *p2) { node *ans = new node(); node *anstail = ans; while (p1 || p2) { if (p1 && p2) { if (p1->val < p2->val) { //选出最小的 node *p = p1->next; anstail->next = p1; anstail = p1; anstail->next == NULL; p1 = p; } else { node *p = p2->next; anstail->next = p2; anstail = p2; anstail->next == NULL; p2 = p; } } else if (p1 && !p2) { if (p1) { anstail->next = p1; return ans->next; } } else { if (p2) { anstail->next = p2; return ans->next; } } } return ans->next; } |
反正链表头插法（正序变逆序）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
node *mergereverse(node *p1, node *p2) { node *ans = NULL; while (p1 || p2) { if (p1 && p2) { if (p1->val < p2->val) { //选出最小的 node *p = p1->next; p1->next = ans; ans = p1; p1 = p; } else { node *p = p2->next; p2->next = ans; ans = p1; p2 = p; } } else if (p1 && !p2) { while (p1) { node *p = p->next; p1->next = ans; ans = p1; p1 = p; } } else { while (p2) { node *p = p2->next; p2->next = ans; ans = p2; p2 = p; } } } return ans; } |