Leetcode算法题（链表的中间节点+返回倒数第k个节点+合并两个有序链表）

题目1：

本题力扣链接：https://leetcode.cn/problems/middle-of-the-linked-list/solutions/164351/lian-biao-de-zhong-jian-jie-dian-by-leetcode-solut/

思路1：单指针法

首先我们对链表进行遍历，记录链表的总长度N，再进行遍历原链表，返回刚跳出循环大于N/2时，对应的链表节点，即为中间节点。

typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) {     ListNode* pcur=head;     if(head==NULL)     {         return head;     }     int count=0;     while(pcur)     {         count++;         pcur=pcur->next;     }     pcur=head;     int k=0;     while(k<count/2)     {         k++;         pcur=pcur->next;     }     return pcur; }

思路2：快慢指针法

typedef struct ListNode ListNode ; struct ListNode* middleNode(struct ListNode* head) {         ListNode* slow = head;         ListNode* fast = head;         while (fast != NULL && fast->next != NULL) {             slow = slow->next;             fast = fast->next->next;         }         return slow;     }

场景1：

场景二：

题目2：

OJ链接：

思路1：反转链表+遍历

先将原链表进行翻转，再将反转后的链表的头结点移动k-1位，最后直接返回此时节点的值。

typedef struct ListNode ListNode; int kthToLast(struct ListNode* head, int k){     //1. 先将原链表进行翻转     //2. 再将反转后的链表的头结点移动k-1位     ListNode* n1,*n2,*n3;     n1=NULL,n2=head,n3=n2->next;     while(n2)     {         n2->next=n1;         n1=n2;         n2=n3;         if(n3)         n3=n3->next;     }     k=k-1;     while(k--)     {         n1=n1->next;     }     return n1->val; } 

复杂度分析：

时间复杂度：O(N),其中N为给定链表节点的数目。

空间复杂度：O(1)

思路2：遍历+挪动

先计算原链表的总长度s，再将原链表的头结点移动s-k位，返回此时节点对应的值。

typedef struct ListNode ListNode; int kthToLast(struct ListNode* head, int k){     ListNode* pcur=head;     int s=0;     while(pcur)     {         s++;         pcur=pcur->next;     }     int m=s-k;     while(m--)     {         head=head->next;     }     return head->val;  }

复杂度分析：

时间复杂度：O(N),其中N为给定链表节点的数目。

空间复杂度：O(1)

题目3：

思路：遍历+尾插+比较

创建新的带头链表，依次遍历两个原链表，比较对应的值，尾插到新的链表尾部。

typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {     if (list1 == NULL) {         return list2;     }     if (list2 == NULL) {         return list1;     }     ListNode* newlist,*newhead;      newhead=newlist=(ListNode*)malloc(sizeof(ListNode));     while (list1 && list2) {         if (list1->val > list2->val) {             newlist->next = list2;             list2 = list2->next;         } else {             newlist->next = list1;             list1 = list1->next;         }         newlist = newlist->next;     }     if (list1)         newlist->next = list1;     if (list2)         newlist->next = list2;     return newhead->next; }

如果本文章对你有帮助，期待你的三连！！！