本章重点
- 链表OJ题
1. 删除链表中等于给定值 val 的所有结点。 OJ链接
思路一：删除头结点时另做考虑（由于头结点没有前一个结点）
struct ListNode* removeElements(struct ListNode* head, int val) { assert(head); struct ListNode* cur = head; struct ListNode* curPrev = NULL; while (cur != NULL) { if (cur->val != val) { curPrev = cur; cur = cur->next; } else { if (cur == head) { head = cur->next; free(cur); cur = head; } else { curPrev->next = cur->next; free(cur); cur = curPrev->next; } } } return head; }
思路二：添加一个虚拟头结点，删除头结点就不用另做考虑
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur = head; struct ListNode* newhead = NULL; struct ListNode* tail = NULL; while (cur != NULL) { if (cur->val == val) { struct ListNode* del = cur; cur = cur->next; free(del); } else { //尾插 if (tail == NULL) { newhead = tail = cur; } else { tail->next = cur; tail = tail->next; } cur = cur->next; } } if (tail)//如果最后一个数是要删除的，tail就需要置空 tail->next = NULL; return newhead; }
2. 反转一个单链表。OJ链接
思路：通过三个指针的操作，每次将当前节点反转并向前移动
struct ListNode* reverseList(struct ListNode* head) { assert(head); struct ListNode* n1, * n2, * n3; n1 = NULL; n2 = head; n3 = n2->next; while (n2) { //翻转 n2->next = n1; //交换 n1 = n2; n2 = n3; //记录位置 if(n2 != NULL) n3 = n3->next; } return n1; }
思路：头插法
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* newhead = NULL; while (cur) { //保存cur下一个结点的位置 struct ListNode* next = cur->next; //头插 next = newhead; newhead = cur; //更新 cur = next; } return newhead; }
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则 返回第二个中间结点。OJ链接
思路：快慢指针的前进方向相同，且它们步伐的「差」是恒定的，使用两个指针变量，刚开始都位于链表的第 1 个结点，一个永远一次只走 1 步，一个永远一次只走 2 步，一个在前，一个在后，同时走。这样当快指针走完的时候，慢指针就来到了链表的中间位置。
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast = head; struct ListNode* slow = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }
4. 输入一个链表，输出该链表中倒数第k个结点。OJ链接
首先让快指针先行k步，然后让快慢指针每次同行一步，直到快指针指向空节点，慢指针就是倒数第K个节点。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) { struct ListNode* fast = pListHead; struct ListNode* slow = pListHead; while (k--)//走k步 { //链表没有k步长，那么此时倒数就是空 if (fast == NULL) return NULL; fast = fast->next; } while (fast) { slow = slow->next; fast = fast->next; } return slow; }
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。OJ链接
思路一：我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (list1 == NULL) return list2; if (list2 == NULL) return list1; struct ListNode* newhead = NULL; struct ListNode* tail = NULL; while (list1 && list2) { //小值给到新链表上 if (list1->val < list2->val) { if (tail == NULL) { newhead = tail = list1; } else { tail->next = list1; tail = tail->next; } list1 = list1->next; } else { if (tail == NULL) { newhead = tail = list2; } else { tail->next = list2; tail = tail->next; } list2 = list2->next; } } if (list1) tail->next = list1; if (list2) tail->next = list2; return newhead; }
【编织时空三：探究顺序表与链表的数据之旅】（下）：https://developer.aliyun.com/article/1424879
