【基础算法】单链表的OJ练习(1) # 反转链表 # 合并两个有序链表 #

前言

• 上一章讲解了单链表 -> 传送门 <- ，后面几章就对单链表进行一些简单的题目练习，目的是为了更好的理解单链表的实现以及加深对某些函数接口的熟练度。

• 本章带来了两个题目。一是反转链表，二是合并两个有序链表，整体难度不大，但要理清解题思路。

反转链表

题目链接 -> 传送门 <-

• 该题目的意思是将一个单链表反转过来，单链表的尾节点变成新的头节点，头节点变成新的尾节点：

• 题目描述是，给你一个单链表的头节点 head ，请你反转链表，并返回反转后的链表。

• 返回反转后的链表也就是返回反转后的链表的头节点。

思路一：

• 创建一个新的链表，取原链表的元素依次头插即可，最后返回这个新的链表的头节点。

思路二：

• 直接修改原链表，返回原链表的尾节点（反转后的头节点）即可。

• 定义三个指针遍历原链表，三个指针 （prev，cur，tail） prev开始指向NULL，cur指向头节点，tail指向cur 的下一个节点(为了找到下一个)。具体操作就是cur->next = prev（将指针改变指向），然后prev = cur，cur = tail，tail = cur->next(该语句在循环的开头)。这样又是三个指针指向不同的节点，然后再将cur的指针指向前一个prev，整个过程其实就是一个循环。

• 循环的条件是cur不为NULL就继续，当cur为空，也就是最后一步cur = tail，此时cur，tail都为空，而prev刚好指向原链表的最后一个节点，所以最后返回prev就可以了。

这里采用思路二进行代码实现：

struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur = head;struct ListNode* prev =  NULL;while (cur){struct ListNode* tail = cur->next;cur->next = prev;prev = cur;cur = tail;}return prev;
}

合并两个有序链表

题目链接 -> 传送门 <-。

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

• 该题与归并排序的排序思路差不多。本题需要创建一个新链表。之后采用双指针分别遍历上下两个链表，那个节点的数据较小，就在新的链表中尾插该节点，然后指向该节点的指针向后移动一位。整体来说就是一个循环，循环结束的条件就是两个指针都指向了NULL或者其中一个指针指向了NULL。

• 注意，我们这里的新链表是不带哨兵位的，当然带哨兵位可能更加方便，最后需要返回哨兵位的下一个节点的指针。

• 如果循环结束后，有一个指针没有指向NULL，那么在后面还需要将剩余的节点依次尾插，直到两个指针都为NULL合并成功。

代码实现：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* l1 = list1, * l2 = list2;  // 两个指针分别指向两个链表的头struct ListNode* head = NULL, * cur = NULL;  // 新链表的头和进行操作的指针curwhile (l1 && l2)   // 有一个指向空就结束{if (l1->val < l2->val)  // 比较数据值{if (!head) head = cur = l1;   // 这个if是如果新链表为空，就将该节点作为头节点else cur->next = l1, cur = cur->next;l1 = l1->next;}else{if (!head) head = cur = l2;else cur->next = l2, cur = cur->next;l2 = l2->next;}}// 如果l1不为空说明l1还有节点没有尾插完，需继续尾插while (l1){if (!head) head = cur = l1;else cur->next = l1, cur = cur->next;l1 = l1->next;}// 如果l2不为空说明l2还有节点没有尾插完，需继续尾插while (l2){if (!head) head = cur = l2;else cur->next = l2, cur = cur->next;l2 = l2->next;}// 最后返回新链表的头节点return head;
}

写在最后

对于单链表的题目练习，最重要的是思路，我们在数据结构阶段要养成画图的习惯，因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。

感谢阅读本小白的博客，错误的地方请严厉指出噢！