leetcode206：反转链表

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        if (head->next != nullptr) cout << "-> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    递归实现

    reverseList 函数：翻转一个链表，并返回新链表的头结点，也是原链表的尾结点。
    1.先递归处理 reverseList(head->next)。
    2.以 head->next 为头结点的链表反转，得到原链表的尾结点 tail，此时 head->next 是新链表的尾结点。
    3.令它的 next 指向 head，并将 head->next 指向空。即可将整个链表反转，新链表的头结点是 tail。
    
    时间复杂度：O(n)
        其中 n 是链表的长度。需要遍历链表一次。
    空间复杂度：O(n)
        总共递归 n 层，系统栈的空间复杂度是 O(n)，
        所以总共需要额外 O(n) 的空间。
*/
class Solution_0 {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* tail = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tail;
    }
};

/*
    迭代实现

    时间复杂度：O(n)
        其中 n 是链表的长度。需要遍历链表一次。
    空间复杂度：O(1)
        只有三个额外变量。
*/
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode *prev = nullptr, *cur = head;
        while (cur != nullptr) {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {1, 2, 3, 4, 5};

    // 创建链表
    ListNode* head = createList(nums);

    // 反转操作
    ListNode* result = solution.reverseList(head);
    // 打印结果
    cout << "Reversed List: ";
    printList(result);

    // 释放内存
    deleteList(result);

    return 0;
}

Golang 代码

package main

import "fmt"

// 定义链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

// createLinkedList 创建链表
func createLinkedList(values []int) *ListNode {
	if len(values) == 0 {
		return nil
	}
	head := &ListNode{Val: values[0]}
	current := head
	for _, val := range values[1:] {
		current.Next = &ListNode{Val: val}
		current = current.Next
	}
	return head
}

// printLinkedList 打印链表
func printLinkedList(head *ListNode) string {
	var result []int
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return fmt.Sprintf("%v", result)
}

/*
    递归是将问题分解为更小的子问题，并通过递归调用函数来解决这些子问题。
    在这个例子中，将链表分为两部分：当前节点和其余部分。
    若链表为空或只有一个节点，则直接返回该节点，因为不需要反转。
    对于其余部分，递归调用 everseList 函数来反转它，并将反转后的头节点存储在 reversedHead 变量中。
    然后，将当前节点的 Next 指针指向前一个节点，并将当前节点的 Next 指针设置为nil，完成反转操作。
    最后，返回反转后的头节点。

    时间复杂度：O(n)
        链表中每个节点只被遍历一次。
    空间复杂度：O(n)
        在递归过程中，使用栈来保存函数的调用信息。
        栈的深度取决于链表的长度，总共递归 n 层，系统栈的空间复杂度是 O(n)，
*/
func reverseList_1(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    // 反转链表（除了当前节点以外的）
    reversedHead := reverseList(head.Next)
    // 将当前节点的 Next 指向前一个节点
    head.Next.Next = head
    head.Next = nil
    
    // 返回反转后的头节点
    return reversedHead
}

/*
    初始化：
        指针 prev 和 curr，分别指向链表的前一个节点和当前节点。
    遍历链表，每次迭代中：
        保存当前节点的下一个节点 next。
        将当前节点的 Next 指针指向 prev。
        更新 prev 为当前节点。
        更新 curr 为 next。
    当遍历结束后，prev 指针将指向反转后的链表的头节点，返回 prev。

    时间复杂度：O(n)
        只遍历一次链表。
    空间复杂度：O(1)
        只有三个额外变量。
*/
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    cur := head

    // 当当前节点不为空时，进行反转操作
    for cur != nil {
        // 保存下一个节点
        next := cur.Next
        // 将当前节点的 Next 指针指向前一个节点
        cur.Next = prev
        // 更新前一个节点为当前节点
        prev = cur
        // 更新当前节点为下一个节点
        cur = next
    }
    // 返回反转后的头节点
    return prev
}

func main() {
    // 测试用例
	testCases := []struct {
		head    []int
		expected []int
	}{
		{
			head:     []int{1, 2, 3, 4, 5},
			expected: []int{5, 4, 3, 2, 1},
		},
		{
			head:     []int{1, 2},
			expected: []int{2, 1},
		},
		{
			head:     []int{},
			expected: []int{},
		},
	}

	for i, tc := range testCases {
		head := createLinkedList(tc.head)
        fmt.Printf("Test Case %d, Input: head = %v\n", i+1, tc.head)
		result := reverseList(head)
		resultStr := printLinkedList(result)
        expectedStr := fmt.Sprintf("%v", tc.expected)
        
        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
	}
}