题目描述

输入一个链表，反转链表后，输出新链表的表头。

示例

// 输入
{1,2,3}
// 返回值
{3,2,1}

// 输入
{}
// 返回值
{}

代码实现

PHP

<?php
/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/
function reverseList($pHead)
{
    $head = null;
    while ($pHead) {
        $tmp = $pHead->next;
        $pHead->next = $head;
        $head = $pHead;
        $pHead = $tmp;
    }
    return $head;
}

Golang

/**
 * [JZ24-简单]反转链表
 *
 * @param head Node类
 * @return Node类
 */
func reverseList(head *Node) *Node {
    var newHead *Node
    var tmp *Node
    for head != nil {
        // 暂存下一个节点
        tmp = head.Next
        // 把新链表挂到原链表后面
        head.Next = newHead
        // 更新新链表
        newHead = head
        // 移动指针
        head = tmp
    }

    return newHead
}

使用栈实现：

/**
 * [JZ24-简单] 反转链表-栈
 *
 * @param head ListNode类
 * @return ListNode类
 */
func reverseList2(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    tmpMap := make([]int, 0)
    for head != nil {
        tmpMap = append([]int{head.Val}, tmpMap...)
        head = head.Next
    }

    rHead := &ListNode{Val: tmpMap[0], Next: nil}
    cHead := rHead
    for i := 1; i < len(tmpMap); i++ {
        tmpHead := &ListNode{Val: tmpMap[i], Next: nil}
        cHead.Next = tmpHead
        cHead = cHead.Next
    }
    return rHead
}