面试不可不会的单链表反转
- 2021 年 2 月 17 日
- 筆記
单链表反转是面试中常考的一道题，这道题看起来简单，但是能一遍写出 bug free 的代码相当不容易，本文主要提供递归和迭代两种解题方法，供大家参考。
题目
举栗
为了便于理解，以 1->2->3->NULL 为栗子，如下图示：
递归解法
链表具有天然的递归性，一个链表例如：1->2->3->NULL，可以看成以值为 1 的节点作为头节点后面挂接一个更短的(以值为 2 的节点为头节点)的链表，即1->更短的链表（以值为2的节点作为头节点），同理以值为2的节点作为头节点后面也挂接一个更更短的链表（以值为3的节点作为头节点）；依次类推，如下图示。
有了这样的思考，链表反转就可以先翻转头节点后面挂接的更短的链表，然后再在翻转后的更短链表的后面挂接之前的头节点。具体如下图示：
Show me the Code
// C语言版本
struct ListNode* reverseList(struct ListNode* head){
/* 特判 */
if (head == NULL || head->next == NULL) {
return head;
}
/* 翻转头节点(节点值为 1 的节点) 后面挂接的链表(以节点值为 2 的节点作为头节点) */
/* 翻转之后变成 3->2 */
struct ListNode *node = reverseList(head->next);
/* 将头节点(节点值为 1 的节点)挂接在翻转之后的链表的后面(也就是节点值为 2 的节点的后面) */
head->next->next = head;
/* 将尾节点的下一节点置空 */
head->next = NULL;
return node;
}
#python3 版本
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
node = self.reverseList(head.next)
head.next.next = head;
head.next = None;
return node;
迭代（双指针）解法
可以用双指针来做，用一个指针 next 记录当前节点的后一节点，另外一个指针 pre 记录当前节点的前一个节点，如果当前节点是头节点，则 pre 为空指针，还是以链表：1->2->3->NULL 为栗子，具体如下图示。
Show me the Code
// C语言版本
struct ListNode* reverseList(struct ListNode* head){
/* 记录当前节点的前一节点 */
struct ListNode* pre = NULL;
while (head != NULL) {
/* 记录当前节点的后一节点 */
struct ListNode* next = head->next;
head->next = pre;
pre = head;
head = next;
}
return pre;
}
// go语言版本
func reverseList(head *ListNode) *ListNode {
var pre *ListNode = nil
for head != nil {
next := head.Next
head.Next = pre;
pre = head
head = next
}
return pre
}
