反转链表、链表的中间结点、合并两个有序链表(leetcode 一题多解)

一、反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一：翻转单链表指针方向

这里解释一下三个指针的作用：

n1：记录上一个节点，如果是第一个就指向空

n2：记录此节点的位置

n3：记录下一个节点的位置，让翻转后能找到下一个节点，防止丢失指针的地址

/** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {if(head == NULL){return NULL;}//初始条件struct ListNode* n1 = NULL,*n2 = head,*n3 = n2->next;//结束条件while(n2){//迭代过程n2->next = n1;n1 = n2;n2 = n3;if(n3)n3 = n3->next;}return n1;
}

思路二:头插法

取原链表节点头插到新链表

/** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* newHead = NULL;while(cur){struct ListNode* next = cur->next;//头插cur->next = newHead;newHead = cur;cur = next;}return newHead;
}

二、链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一：单指针法

时间复杂度：O(N*1.5)，其中 N 是给定链表的结点数目。
空间复杂度：O(1)，只需要常数空间存放变量和指针。

我们可以对链表进行两次遍历。第一次遍历时，我们统计链表中的元素个数 N；第二次遍历时，我们遍历到第 N/2 个元素（链表的首节点为第 0 个元素）时，将该元素返回即可。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {int n = 0;struct ListNode*cur = head;while(cur != NULL){++n;cur = cur->next;}int k = 0;cur = head;while(k < n/2){++k;cur = cur->next;}return cur;
}

思路二：快慢指针法

时间复杂度：O(N)，其中 N 是给定链表的结点数目。
空间复杂度：O(1)，只需要常数空间存放 slow 和 fast 两个指针。

我们可以优化思路一，用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow = head,*fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

三、合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一（迭代法）:

定义一个头指针和一个尾指针，从小到大依次尾插，直到一个链表为空时结束

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if(l1 == NULL)    return l2;if(l2 == NULL)return l1;struct ListNode* head = NULL, *tail = NULL;while(l1 != NULL && l2 != NULL){if(l1->val < l2->val){//尾插if(tail == NULL){head = tail = l1;}else{tail->next = l1;tail = tail->next;}l1 = l1->next;}else{if(tail == NULL){head = tail = l2;}else{tail->next = l2;tail = tail->next;}l2 = l2->next;}}if(l1)tail->next= l1;if(l2)tail->next= l2;return head;
}

优化一:

先确定头结点，然后再循环判断val大小，尾插

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if(l1 == NULL)    return l2;if(l2 == NULL)return l1;struct ListNode* head = NULL, *tail = NULL;//先确定头节点if(l1->val < l2->val){head = tail =l1;l1 = l1->next;}else{head = tail =l2;l2 = l2->next;}while(l1 && l2){//尾插if(l1->val < l2->val){   tail->next = l1;l1 = l1->next;}else{tail->next = l2;l2 = l2->next;}tail = tail->next;}if(l1)tail->next= l1;if(l2)tail->next= l2;return head;
}

优化二:

设置一个哨兵位的头节点，然后再去尾插。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if(l1 == NULL)    return l2;if(l2 == NULL)return l1;struct ListNode* head = NULL, *tail = NULL;//哨兵位的头节点head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));while(l1 && l2){//尾插if(l1->val < l2->val){   tail->next = l1;l1 = l1->next;}else{tail->next = l2;l2 = l2->next;}tail = tail->next;}if(l1)tail->next= l1;if(l2)tail->next= l2;struct ListNode* first = head->next;free(head);return first;
}

思路二（递归法）：

（这是题解中大佬的一个解法）以迭代的思路写递归，尤为惊人！！！

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){/*if判断：1.如果l1为空，返回l22.如果l2为空，返回l13.如果l1的值小于l2，比较l1的next值和l2，并把值赋给l1的下一个；返回l14.反之，比较l1和l2的next值，并把值赋给l2的下一个；返回l2*/if (l1 == NULL) {return l2;} else if (l2 == NULL) {return l1;} else if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}
}