每天进步一点点🤏

反转链表

  • 1019 字

反转链表

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
给你单链表的头节点 head,请你反转链表,并返回反转后的链表

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
思路:
使用两个链表,遍历链表时,链表A负责记录当前节点,链表B负责将当前节点记录为自己的子节点,
让后A=B,新建B,循环直到链表走完

代码:
class ListNode
{
    public $val = 0;
    /**
     * @var ListNode|null
     */
    public $next = null;

    function __construct($val = 0, $next = null)
    {
        $this->val  = $val;
        $this->next = $next;
    }
}

/**
 * @param ListNode $head
 *
 * @return ListNode
 */
function reverseList($head)
{
    $listA = new ListNode();
    $listB = new ListNode();
    while ($head) {
        // 链表A记录当前节点的值
        $listA->val  = $head->val;
        // 链表B将当前节点作为下一个节点
        $listB->next = $listA;
        // 将链表A替换为链表B
        $listA       = $listB;
        $listB       = new ListNode();

        $head = $head->next;
    }

    // 返回链表->next,不然链表的表头会是0
    return $listA->next;
}