这两天比较闲，因此刷了几道HackerRank上的题目。下面简单将其中与单链表操作有关的题目集中总结一下。
首先给出这些题目中通用的单链表节点定义：
|
1 2 3 4 5 |
struct Node { int data; struct Node *next; } |
第一题：顺序打印单链表中的元素。
思路：从头节点处开始遍历输出，直至NULL。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
void Print(Node *head) { if (head == NULL) { return; } Node *ptr = head; while(ptr != NULL) { cout << ptr->data << endl; ptr = ptr->next; } } |
第二题：给定一个数值，生成一个新数值并插入到单链表的尾部。
思路：遍历到尾节点，然后创建一个新的节点，让尾节点的next指针指向这个新的节点。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Node* Insert(Node *head,int data) { Node *newCell = (Node *)malloc(sizeof(Node)); newCell->data = data; newCell->next = NULL; if (head == NULL) { return newCell; } else { Node *tail = head; while(tail->next != NULL) { tail = tail->next; } tail->next = newCell; return head; } } |
第三题：给定一个数值，生成一个新节点插入到单链表的头部。
思路：创建一个新的节点，让这个新节点的next指针指向原来链表的头部。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Node* Insert(Node *head,int data) { Node *newCell = (Node *)malloc(sizeof(Node)); newCell->data = data; if (head == NULL) { newCell->next = NULL; return newCell; } else { newCell->next = head; return newCell; } } |
第四题：给定一个位置和数据，生成一个新节点并插入到单链表的相应位置处。
思路：保持一个计数器，然后开始遍历单链表，同时计数器进行更新，当计数器的值与位置相等时，表示找到了要插入的位置了，之后的做法类似于第三题。
代码：
|
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 |
Node* InsertNth(Node *head, int data, int position) { Node *newCell = (Node *)malloc(sizeof(Node)); newCell->data = data; if (head == NULL) { newCell->next = NULL; return newCell; } else { if (position == 0) { newCell->next = head; return newCell; } else { int i = 1; Node *ptr = head; while(ptr != NULL && i != position) { i++; ptr = ptr->next; } newCell->next = ptr->next; ptr->next = newCell; return head; } } } |
第五题：从单链表中删除一个给定位置处的节点。
思路：很简单，不多说了。
代码：
|
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 |
Node* Delete(Node *head, int position) { if (head == NULL) { return NULL; } else { Node *ptrToNode; if (position == 0) { ptrToNode = head->next; free(head); return ptrToNode; } else { int i = 1; ptrToNode = head; while(ptrToNode != NULL && i != position) { i++; ptrToNode = ptrToNode->next; } Node *temp = ptrToNode->next; ptrToNode->next = temp->next; free(temp); return head; } } } |
第六题：逆序打印单链表中的元素。
思路：使用递归。
代码：
|
1 2 3 4 5 6 7 8 9 10 |
void ReversePrint(Node *head) { if(head) { ReversePrint(head->next); cout << head->data << endl; } else { return; } } |
第七题：将一个单链表中的所有元素逆序。
思路：首先需要确定这个单链表是带有头节点的还是不带有头节点的，带有头节点的链表在处理起来稍微复杂一点。然后可以用三个指针，分别指向当前节点cur，前一个节点pre，后一个节点next，然后调整这三个节点之间的指向关系。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Node* Reverse(Node *head) { if (head == NULL) { return NULL; } else { Node *reverseHead = NULL; Node *cur = head; Node *pre = NULL; Node *next = NULL; while(cur != NULL) { next = cur->next; if (next == NULL) { reverseHead = cur; } cur->next = pre; pre = cur; cur = next; } return reverseHead; } } |
第八题：比较两个单链表中的元素是否相同
思路：用两个指针分别遍历两个链表，然后比较指针指向的节点数值是否相等。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
int CompareLists(Node *headA, Node* headB) { if(headA == NULL && headB == NULL) { return 0; } else if ((!headA && headB) || (headA && !headB)){ return 0; } else { Node *ptrToA = headA, *ptrToB = headB; while(ptrToA && ptrToB && (ptrToA->data == ptrToB->data)) { ptrToA = ptrToA->next; ptrToB = ptrToB->next; } if(ptrToA == NULL && ptrToB == NULL) { return 1; } else { return 0; } } } |
第九题：合并两个有序单链表，将合并的结果放在一个新链表中。
思路：用两个指针来分别遍历两个链表，比较这两个指针指向的节点的数值大小，
若A<B,那么A++,拷贝A的数据到C,直到A>B;若A>B,则B++,拷贝B的数据到C,直到B>A;若A==B,则A++,B++,拷贝A或B到C。若其中一条链表先遍历完，则将另一条链表的数据直接拷贝到C中。
代码：
|
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
Node* MergeLists(Node *headA, Node* headB) { if (headA == NULL && headB == NULL) { return NULL; } else if (! headA && headB) { return headB; } else if (headA && !headB) { return headA; } else { Node *ptrToA = headA, *ptrToB = headB; Node *cur = (Node *)malloc(sizeof(Node)); Node *head = cur; while(ptrToA && ptrToB) { while(ptrToA && ptrToB && (ptrToA->data < ptrToB->data)) { Node *newCell = (Node *)malloc(sizeof(Node)); newCell->data = ptrToA->data; cur->next = newCell; cur = newCell; ptrToA = ptrToA->next; } while(ptrToA && ptrToB && (ptrToA->data > ptrToB->data)) { Node *newCell = (Node *)malloc(sizeof(Node)); newCell->data = ptrToB->data; cur->next = newCell; cur = newCell; ptrToB = ptrToB->next; } while(ptrToA && ptrToB && (ptrToA->data == ptrToB->data)) { Node *newCell = (Node *)malloc(sizeof(Node)); newCell->data = ptrToA->data; cur->next = newCell; cur = newCell; ptrToA = ptrToA->next; ptrToB = ptrToB->next; } } if(!ptrToA && ptrToB) { while(ptrToB) { Node *newCell = (Node *)malloc(sizeof(Node)); newCell->data = ptrToB->data; cur->next = newCell; cur = newCell; ptrToB = ptrToB->next; } cur->next = NULL; } else if(ptrToA && !ptrToB) { while(ptrToA) { Node *newCell = (Node *)malloc(sizeof(Node)); newCell->data = ptrToA->data; cur->next = newCell; cur = newCell; ptrToA = ptrToA->next; } cur->next = NULL; } else if (!ptrToA && !ptrToB ) { cur->next = NULL; } return head->next; } } |
第十题：获得离一个链表尾部距离为K的节点。
思路：设置两个指针，初始化时均指向头节点，然后让一个指针先往前移动K个节点，然后这两个指针再一起向前移动，当第一个指针指向链表的尾部时，第二个节点所指的位置正好就是离尾部距离为K的节点。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
int GetNode(Node *head,int positionFromTail) { // This is a "method-only" submission. // You only need to complete this method. Node *p, *cur; p = cur = head; for(int i = 0; i <= positionFromTail;i++) { if (p != NULL) { p = p->next; } } while(p) { cur = cur->next; p = p->next; } return cur->data; } |
第十一题：删除一个有序单链表中的重复元素。
思路：用两个指针分别指向当前节点cur和下一节点fol，当fol和cur的数值相等时，fol++，直到不再相等，调整cur和fol，然后cur++。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Node* RemoveDuplicates(Node *head) { if(head == NULL) { return NULL; } else { Node *cur = head, *fol = cur->next; while(fol != NULL) { while(fol && (fol->data == cur->data)) { fol = fol->next; } cur->next = fol; if(fol) { cur = fol; fol = cur->next; } } return head; } } |
第十二题：检测链表中是否有环。
思路：使用两个指针，一个指针每次往前移动一个节点，一个指针每次往前移动两个节点，若是链表中有环的话，那么这两个指针一定会相遇，因此可以用这两个指针是否会相等来检测链表中有没有环。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
bool has_cycle(Node* head) { if(head == NULL) { return false; } else { Node *p = head, *q = head; while(p && q && q->next) { q = q->next->next; p = p->next; if(p == q) { return true; } } return false; } } |
第十三题：找到两个链表的合并点。
思路：首先计算出这两个链表的长度和长度差，然后设置两个指针分别指向这两个链表的头部，让长的那个指针先移动长度差个节点，然后两个指针再一起向前移动，当这两个指针相等的时候，所指的点就是这两个链表的合并点。
代码：
|
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 |
int FindMergeNode(Node *headA, Node *headB) { Node *ptrToA = headA,*ptrToB = headB; int lenA,lenB; lenA = lenB = 0; while(ptrToA) { lenA++; ptrToA = ptrToA->next; } while(ptrToB) { lenB++; ptrToB = ptrToB->next; } ptrToA = headA,ptrToB = headB; if(lenA < lenB) { Node *temp = ptrToB; ptrToB = ptrToA; ptrToA = temp; int x = lenA; lenA = lenB; lenB = x; } for(int i = 0; i < lenA-lenB;i++) { ptrToA = ptrToA->next; } while(ptrToA && ptrToA != ptrToB) { ptrToA = ptrToA->next; ptrToB = ptrToB->next; } return ptrToA->data; } |
第十四题：向一个有序双向链表中插入一个节点。
思路：和向单链表中插入节点思路相同，只不过节点的前后关系设置多了几步。
代码：
|
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 35 36 |
Node* SortedInsert(Node *head,int data) { Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = data; if(head == NULL) { newNode->next = NULL; newNode->prev = NULL; return newNode; } else { if(data < head->data) { newNode->next = head; head->prev = newNode; newNode->prev = NULL; return newNode; } else { Node *ptr = head,*cur; while(ptr && (data > ptr->data)) { cur = ptr; ptr = ptr->next; } if(! ptr) { cur->next = newNode; newNode->next = NULL; newNode->prev = cur; return head; } else { cur->next = newNode; newNode->next = ptr; newNode->prev = cur; ptr->prev = newNode; } return head; } } } |
第十五题：逆序一个双向链表。
思路：和逆序一个单链表思路一致，并且由于节点中本身就有prev和next信息，因此只需要用一个指针指向当前节点即可。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Node* Reverse(Node* head) { if (head == NULL) { return NULL; } Node *cur = head, *next = NULL,*reversedHead = NULL; while(cur) { next = cur->next; if (next == NULL) { reversedHead = cur; } cur->next = cur->prev; cur->prev = next; cur = next; } return reversedHead; } |