数据结构与算法⑤(第二章OJ题，上)前五道链表面试题（上）：https://developer.aliyun.com/article/1513343
普通思路的代码：
struct ListNode* middleNode(struct ListNode* head){ struct ListNode*cur=head; int count=0; while(cur!=NULL) { cur=cur->next; count++;//计算链表长度 } struct ListNode*middle=head; for(int i=0;i<count/2;i++)//如5的话3次，6的话4次 { middle=middle->next; } return middle; }
这样的时间复杂度是N+N/2 虽然还是O(N)
但是以后面试可能会要求只能遍历一遍数组呢，这时就要用到快慢指针的思想了
虽然以前有用过，但是变一下就想不到了，看到这个思路又是震惊的一天...
运用快慢指针的代码：
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast = head , * slow = head; while (fast!=NULL&&fast->next!=NULL) { fast=fast->next->next;//快指针一次走两步 slow=slow->next;//慢指针一次走一步 } return slow; }
4. 输出该链表中倒数第k个结点
剑指 Offer 22. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，
本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。
这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* getKthFromEnd(struct ListNode* head, int k){ }
（这题没给范围，有点不严谨，但是懂思路就好了）
力扣这题是后更新的，所以测试用例更不严谨
这里说一下，力扣应该是OJ题做的最好的，但是面试那些应该用牛客多一点。
普通思路的代码：
这题和上一题的普通思路一样，相当于遍历两次链表
struct ListNode* getKthFromEnd(struct ListNode* head, int k){ struct ListNode*cur=head; int count=0; while(cur!=NULL) { cur=cur->next; count++;//计算链表长度 } struct ListNode*newHead=head; for(int i=0;i<count-k;i++) { newHead=newHead->next; } return newHead; }
写完普通思路我想着用快慢指针怎么用，想了几秒就觉得不行就不想了，以为不能用
（不想动太多脑的坏处）看到别人的思路我已经开始咬嘴唇了...
虽然觉得k不一样时，时间一样，但是帅就对了：
运用快慢指针的代码：
struct ListNode* getKthFromEnd(struct ListNode* head, int k){ struct ListNode* fast = head , * slow = head; while(k--) { if(fast==NULL) { return NULL; } fast=fast->next;//快指针先走k步 } while(fast) { fast=fast->next; slow=slow->next;//快慢指针一起走 } return slow; }
5. 合并两个有序链表为一个新的有序链表
21. 合并两个有序链表
难度简单
将两个升序链表合并为一个新的 升序 链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
- 两个链表的节点数目范围是 [0, 50]
- -100 <= Node.val <= 100
- l1 和 l2 均按 非递减顺序 排列
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ }
尾插法代码：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (list1 == NULL) { return list2; } if (list2 == NULL) { return list1; } struct ListNode* cur=NULL; if(list1->val <= list2->val) { cur = list1; list1 = list1->next; } else { cur = list2; list2 = list2->next; } struct ListNode* new = cur; while (list1 && list2) { if (list1->val <= list2->val) { cur->next = list1; cur = list1; list1 = list1->next; } else { cur->next = list2; cur = list2; list2 = list2->next; } } if (list1 == NULL) { cur->next = list2; } else { cur->next = list1; } return new; }
尾插法+哨兵位的头节点代码：
哨兵位的头节点就是不存数据的节点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (list1 == NULL) { return list2; } if (list2 == NULL) { return list1; } struct ListNode* cur = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* new = cur; while (list1 && list2) { if (list1->val <= list2->val) { cur->next = list1; cur = list1; list1 = list1->next; } else { cur->next = list2; cur = list2; list2 = list2->next; } } if (list1 == NULL) { cur->next = list2; } else { cur->next = list1; } struct ListNode* newHead = new->next; free(new); return newHead; }
本篇完。
后面还有接着这部分的较难的OJ题
