# 后端 链表总结

hano65535 · October 18, 2019 · 0 hits

## 单向链表

### 单向链表的基本操作

 `123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566` `typedef int ElmeType;typedef struct Lnode{ ElemType val; struct Lnode next;}Lnode;//构造线性表,头插法，将节点插入到表头，这样构成的线性表就是与输入的顺序相反Lnode (Lnode Lhead, int v){ Lnode *newNode = (Lnode *)malloc(sizeof(Lnode)); if (newNode == NULL){ fprintf(stderr, "malloc failuren"); exit(EXIT_FAILURE); } newNode->val = v; newNode->next = NULL; newNode->next = Lhead; Lhead = newNode; return Lhead;}//尾插法Lnode *addListR(Lnode *Lhead, Elemtype v){ Lnode *newNode = (Lnode *)malloc(sizeof(Lnode)); if (newNode == NULL){ fprintf(stderr, "malloc failuren"); exit(EXIT_FAILURE); } newNode->val = v; newNode->next = NULL; Lnode *front = NULL, *rear = NULL; if (front == NULL) front = newNode; else rear->next = newNode; rear = newNode; return front;}//本算法取出单链表L（带头结点）中第i个位置的结点指针LNode GetElemAddr(Lnode* h, ElemType i){ int j=1; //计数，初始为1 LNode p = h; //头结点指针赋给p if(i == 1) return L; //若i等于1，则返回头结点 if(i < 1) return NULL; //若 i 无效，则返回 NULL while( p && j < i ) { //从第1个结点开始找，查找第i个结点 p=p->next; j++; } return p; //返回第i个结点的指针，如果i大于表长，p=NULL，直接返回p即可}//本算法查找单链表 L （带头结点）中数据域值等于e的结点指针，否则返回NULLLNode *LocateElem (Lnode *h, ElemType e) { LNode *p= h; while( p != NULL && p->data !=e) //从第1个结点开始查找data域为e的结点 p=p->next; return p; //找到后返回该结点指针，否则返回NULL}`

### 插入操作

 `1234` `//将s节点插入到第i个位置Lnode temp = GetElemAddr(h, i-1);s->next = temp->next;temp->next = s;`

 `123456` `//将结点插入到*P之前的主要代码片段s->next = p->next; //修改指针域，不能颠倒p->next = s;temp = p->data; //交换数据域部分p->data=s->data;s->data=temp;`

wiki 中实现的双向链表

## 链表的相关面试题

 `1234567891011121314151617` `class Solution {public: ListNode* reverseList(ListNode* head) { ListNode* newHead = NULL; ListNode* temp =NULL; //存储当前要反转的节点 while(head != NULL){ temp = head; head = head->next //尾插法 temp->next = newHead; newHead = temp; } return newHead; }};`

 `123456789101112131415161718192021222324252627282930` `class Solution {public: ListNode* reverseBetween(ListNode* head, int m, int n) { ListNode start = NULL, *temp = NULL; ListNode dummy(0); dummy.next = head; ListNode *prev = &dummy; if (head == NULL || head->next== NULL || m == n) return head; int i = 1; for( ;i < m; i++) prev = prev->next; start = prev->next; for(; m < n; m++){ temp = start->next; start->next = temp->next; temp->next = prev->next; prev->next = temp; } return dummy.next; }};`

### Rotate List

 `12345678910111213141516171819202122232425262728293031323334` `/ * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode rotateRight(ListNode* head, int k) { if (head == NULL || head->next == NULL || k == 0) return head; ListNode *prev = head; int len = 1; //prev指向尾节点 while(prev->next != NULL){ prev = prev->next; len++; } k = len - k % len; prev->next = head; //首尾相连 while(k > 0){ prev = prev->next; k--; } head = prev->next; prev->next = NULL; return head; }};`

### Copy List with Random Pointer

 `123456789101112131415161718192021222324252627282930313233343536373839404142` `/** * Definition for singly-linked list with a random pointer. * struct RandomListNode { * int label; * RandomListNode *next, *random; * RandomListNode(int x) : label(x), next(NULL), random(NULL) {} * }; */class Solution {public: RandomListNode *copyRandomList(RandomListNode *head) { if (head == NULL) return NULL; map ma; RandomListNode *newHead = new RandomListNode(head->label); ma.insert(make_pair(head, newHead)); RandomListNode *p = head->next; RandomListNode *q = newHead; //构造新链表 while(p){ //产生新节点，插入到新链表中 RandomListNode *temp = new RandomListNode(p->label); q->next = temp; ma.insert(make_pair(p, temp)); p = p->next; q = q->next; } //拷贝随机指针 p = head; q = newHead; while(p){ q->random = ma[p->random]; p = p->next; q = q->next; } return newHead; }};`

(2) 更新新插入节点的随机指针
(3) 分离两个链表

 `12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667` `/** * Definition for singly-linked list with a random pointer. * struct RandomListNode { * int label; * RandomListNode *next, *random; * RandomListNode(int x) : label(x), next(NULL), random(NULL) {} * }; */class Solution {public: RandomListNode *copyRandomList(RandomListNode *head) { if (head == NULL) return NULL; RandomListNode *p = head; //构造成a->a'->b->b'->c->c'..... while(p){ RandomListNode *temp = new RandomListNode(p->label); temp->next = p->next; p->next = temp; p = p->next->next; } p = head; //更新随机指针 while(p){ if (p->random) p->next->random = p->random->next; p = p->next->next; } /* //分离链表 p = head; RandomListNode *newHead = p->next; while(p){ RandomListNode *q = p->next; RandomListNode *temp = p->next->next; if(temp == NULL){ //此时到达最后一个节点temp == NULL p->next = NULL; q->next = NULL; }else{ q->next = temp->next; p->next = temp; } p= p->next; }*/ //分离链表 p = head; RandomListNode *newHead = p->next; while(p){ RandomListNode *q = p->next; p->next = q->next; //考虑这种情况d -> d'-> NULL,是否到达末端 if (q->next) q->next = q->next->next; p= p->next; } return newHead; }};`

### Sort List

(1) 要归并，首先得求链表的中点，在中点处将链表断开
(2) 合并两个已经排好序的链表

 `1234567891011121314151617181920` `/* *一种不好的求中点的方法,这种方法的缺点在于当只有两个节点的时候，例如a->b, *返回的是a->b, NULL的划分(这个会对以后的合并造成很大的影响)，而需要的则是 *a，b的划分 */ListNode *getMiddle(ListNode *h){ if (head == NULL && head->next == NULL) return head; ListNode *fast, *slow; slow = fast = head; while(fast && fast->next){ slow = slow->next; fast = fast->next->next; } return slow;}`

 `12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455` `/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* sortList(ListNode* head) { if(!head || !head->next) return head; //找到中间节点 ListNode dummy(-1); dummy.next = head; ListNode *slow, *fast; slow = fast = &dummy; while(fast && fast->next){ slow = slow->next; fast = fast->next->next; } //从中间分开 ListNode *middle = slow->next; slow->next = nullptr; ListNode *h1 = sortList(head); ListNode *h2 = sortList(middle); return merge(h1, h2); }private: ListNode *merge(ListNode *l1, ListNode *l2){ ListNode dummy(-1); ListNode *p = &dummy; while(l1 && l2){ if(l1->val <= l2->val){ p->next = l1; l1= l1->next; }else{ p->next = l2; l2 = l2->next; } p = p->next; } if(l1 == nullptr) p->next = l2; else p->next = l1; return dummy.next; }}；`