LeetCode 206. Reverse Linked List

from typing import Optional

import pytest


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 初始化前一个节点为None，因为反转后的最后一个节点将指向None
        prev = None
        # 初始化当前节点为链表的头节点
        current = head

        # 迭代链表，直到当前节点为None，即遍历完整个链表
        while current:
            # 保存下一个节点的引用，以便在反转后重新连接
            next_node = current.next
            # 将当前节点的指针反向指向前一个节点
            current.next = prev
            # 更新prev为当前节点，以便下一轮迭代使用
            prev = current
            # 更新current为下一个节点，继续迭代
            current = next_node

        # 当循环结束时，prev将成为新的头节点，即反转后的链表的头部
        return prev

    def reverseListRecursively(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 递归的终止条件：当链表为空或只有一个节点时，无需反转，直接返回
        if not head or not head.next:
            return head

        # 递归地反转子链表
        new_head = self.reverseListRecursively(head.next)

        # 将当前节点的下一个节点的指针指向当前节点，实现反转
        head.next.next = head
        head.next = None

        return new_head


@pytest.fixture
def solution():
    return Solution()


def test_reverse_list_case(solution):
    head2 = ListNode(1, ListNode(2))
    reversed_head2 = solution.reverseListRecursively(head2)
    assert reversed_head2.val == 2
    assert reversed_head2.next.val == 1
    assert reversed_head2.next.next is None


test_data = [
    (ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))),
     [5, 4, 3, 2, 1]),
    (ListNode(1, ListNode(2)), [2, 1]),
    (None, [])
]


def clone_linked_list(head):
    """实用功能，用于克隆链表。"""
    if not head:
        return None
    return ListNode(head.val, clone_linked_list(head.next))


@pytest.mark.parametrize("method_name", ["reverseList", "reverseListRecursively"])
@pytest.mark.parametrize("input_head, expected_values", test_data)
def test_reverse_list(solution, method_name, input_head, expected_values):
    cloned_head = clone_linked_list(input_head)
    method = getattr(solution, method_name)
    reversed_head = method(cloned_head)

    current = reversed_head
    for expected_val in expected_values:
        assert current.val == expected_val
        current = current.next
    assert current is None


if __name__ == '__main__':
    pytest.main()

package lc

import (
	"reflect"
	"testing"
)

// Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode = nil
	current := head

	// 遍历链表
	for current != nil {
		// 先保存当前节点的下一个节点
		next := current.Next
		// 将当前节点的 Next 指向 prev
		current.Next = prev
		// 更新 prev 为当前节点
		prev = current
		// 移动到下一个节点
		current = next
	}

	return prev
}

func reverseListRecursively(head *ListNode) *ListNode {
	// 如果链表为空，或者链表只有一个节点，那么直接返回该节点。
	if head == nil || head.Next == nil {
		return head
	}

	// 递归调用，处理链表中的下一个节点。
	// newHead 将会是反转后链表的头节点。
	newHead := reverseListRecursively(head.Next)

	// 当前节点的下一个节点（即head.Next）已经被递归地反转了。
	// 我们将下一个节点的 Next 指向当前节点，实现反转。
	head.Next.Next = head

	// 由于当前节点已经被反转，它不再指向原来的下一个节点，所以将 Next 设置为 nil。
	head.Next = nil

	// 返回新的头节点。
	return newHead
}

// 辅助函数：将切片转化为链表
func sliceToList(nums []int) *ListNode {
	if len(nums) == 0 {
		return nil
	}
	head := &ListNode{Val: nums[0]}
	current := head
	for _, v := range nums[1:] {
		current.Next = &ListNode{Val: v}
		current = current.Next
	}
	return head
}

// 辅助函数：将链表转化为切片
func listToSlice(node *ListNode) []int {
	var res []int
	current := node
	for current != nil {
		res = append(res, current.Val)
		current = current.Next
	}
	return res
}

func TestReverseList(t *testing.T) {
	tests := []struct {
		input  []int
		output []int
	}{
		{
			input:  []int{1, 2, 3, 4, 5},
			output: []int{5, 4, 3, 2, 1},
		},
		{
			input:  []int{1, 2},
			output: []int{2, 1},
		},
		{
			input:  []int{},
			output: []int{},
		},
	}

	for _, test := range tests {
		head := sliceToList(test.input)
		got := listToSlice(reverseList(head))
		if len(test.input) == 0 && len(got) == 0 {
			continue
		}
		if !reflect.DeepEqual(got, test.output) {
			t.Errorf("For input %v, expected %v, but got %v", test.input, test.output, got)
		}
	}
}

func TestReverseListRecursively(t *testing.T) {
	tests := []struct {
		input  []int
		output []int
	}{
		{
			input:  []int{1, 2, 3, 4, 5},
			output: []int{5, 4, 3, 2, 1},
		},
		{
			input:  []int{1, 2},
			output: []int{2, 1},
		},
		{
			input:  []int{},
			output: []int{},
		},
	}

	for _, test := range tests {
		head := sliceToList(test.input)
		got := listToSlice(reverseListRecursively(head))
		if len(test.input) == 0 && len(got) == 0 {
			continue
		}
		if !reflect.DeepEqual(got, test.output) {
			t.Errorf("For input %v, expected %v, but got %v", test.input, test.output, got)
		}
	}
}