反转链表

描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000 要求：空间复杂度 O(1)，时间复杂度 O(n)。

如当输入链表{1,2,3}时， 经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。 以上转换过程如下图所示：

示例1:

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

示例2

输入：{}
返回值：{}
说明：空链表则输出空

解法一：用栈实现

• 通过栈先进后出的原理实现链表的反转

import java.util.Stack;
public class Solution {
 public ListNode ReverseList(ListNode head) {
        // 1、创建一个栈
        Stack<ListNode> stack= new Stack<>();
        // 2、遍历链表，把链表节点全部放到栈中
        while (head != null) {
            // 入栈操作
            stack.push(head);
            head = head.next;
        }
        // 栈判空
        if (stack.isEmpty()){
            return null;
        }

        // 3、返回栈顶元素
        ListNode node = stack.pop();
        // 4、定义返回的结果
        ListNode dummy = node;

        //5、遍历栈，栈中的结点全部出栈，然后重新连成一个新的链表
        while (!stack.isEmpty()) {

            // 指向出栈的元素
            node.next = stack.pop();
            // 下一个元素
            node = node.next;
        }
        //最后一个结点指向null
        node.next = null;
        return dummy;
    }
}

复杂度分析

• 时间复杂度：遍历操作O(N)
• 空间复杂度：栈内存空间O(N)

解法二：头插法创建新链表

• 遍历旧链表，每次在新链表头结点处插入创建新链表

public ListNode ReverseList(ListNode head) {

        // 1、创建新链表
        ListNode newHead=null;
        // 2、接受当前节点
        ListNode cur=head;
        // 3、遍历旧链表
        while(cur!=null){
            // 4、临时保存下一节点
            ListNode temp=cur.next;
            // 5、当前节点，指向新链表头结点
            cur.next=newHead;
            // 6、更新新链表头结点
            newHead=cur;
             // 7、下一节点
            cur=temp;

        }
        return newHead;
    }