每日算法题【链表】：链表的中间节点、返回倒数第k个节点、合并两个有序链表

(8) 返回链表的中间节点

• [876. 链表的中间结点 - 力扣（LeetCode）]:

• 解题思路：

  使用快慢指针，快指针走两步，慢指针走一步，快指针指向空，慢指针所指向的节点就是中间节点

  /*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///使用快慢指针，快指针走两步，慢指针走一步，快指针指向空，慢指针所指向的节点就是中间节点
  struct ListNode* middleNode(struct ListNode* head) {//定义两个指针struct ListNode* fast = head;struct ListNode* slow = head;//循环条件判断：fast->next不能放在前面，因为如果链表是偶数个节点，fast最后一次会直接走到空while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
  }
  

(9)输入一个链表，输出该链表中倒数第k个结点

• [面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）]:

• 解题思路：

  定义两个前后指针，之间相差k步，当后指针指为空的时候，前指针所指向的节点就是目标节点。

  /*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
  //定义两个前后指针，之间相差k步，当后指针指为空的时候，前指针所指向的节点就是目标节点。int kthToLast(struct ListNode* head, int k) {struct ListNode *first = head;struct ListNode *last = head;// 先让last向前移动k步for (int i = 0; i < k; i++) {if (last == NULL) {return -1; // 处理k大于链表长度的情况}last = last->next;}// 然后first和last一起移动，直到last为NULLwhile (last != NULL) {first = first->next;last = last->next;}return first->val;
  }
  

(10)合并两个有序链表

• [21. 合并两个有序链表 - 力扣（LeetCode）]:

• 解题思路：

  循环遍历比较两个链表，谁小谁就尾插到新链表当中，谁尾插谁加加，最后再判断一下有没有没比的，全放在新链表的最后

  /*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
  struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {// 创建一个虚拟头节点struct ListNode dummy;struct ListNode* tail = &dummy;dummy.next = NULL;// 循环遍历比较while(list1 && list2){if(list1->val < list2->val){tail->next = list1;list1 = list1->next;} else {tail->next = list2;list2 = list2->next;}tail = tail->next;}// 连接剩余节点if(list1 != NULL){tail->next = list1;} else {tail->next = list2;}return dummy.next;
  }