数据结构习题--反转链表

数据结构习题–反转链表

给你一个链表，请你反转该链表并返回该链表的头结点

方法：双链表求解

分析

题目中给的链表是单链表，实现链表反转，我们可以让后面一个结点指向前面一个结点，但是因为是单链表，所以我们这里人为的引入了两个结点的指针，完成指向前面的结点，并完成对后面结点的更新

注意：

1. 循环结束条件和返回头结点的关系(下面代码循环结束时，head指向null，所以返回其前面的结点 preNode)
2. 在创建preNode时，是让其指向null，而不是直接新建一个结点，否则会让其第一个结点指向我们新建的那个结点，而不是null(因为反转后第一个结点相当于最后一个结点，其next应该指向null)

代码

package LinkList;

public class reverseList {
    /**
     *     nextNode 保存该结点的下一个结点的指针
     *     preNode 记录上一个结点的位置
     */
    public class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }
    class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode nextNode = null;
            // 注意这里 preNode 是指向 null ，而不是新建一个结点
            // 新建一个结点会相当于多添加了一个元素
            ListNode preNode = null;
            while (head!= null){
                // 用 nextNode 来保存结点的下一个位置
                nextNode = head.next;
                // 把当前结点的next指针指向上一个结点
                head.next = preNode;
                // 更新上一个结点，把preNode更新到当前结点的位置
                preNode = head;
                // 把结点更新到当初保存的下一个结点
                head = nextNode;
            }
            return preNode;
        }
    }
}

方法：栈

分析

链表的反转是老生常谈的一个问题了，同时也是面试中常考的一道题。其中最简单的一种方式就是使用栈，因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。原理如下

1. 先依序存入栈
2. 然后拿出一个结点作为头结点，并单独设置一个结点存储其位置，因为后面返回的是头结点
3. 当栈不为空时，依次取出结点，并实现连接
4. 把最后一个结点的next指针指向 null，否则会形成环

代码

public ListNode reverseList(ListNode head) {
    Stack<ListNode> stack = new Stack<>();
    //把链表节点全部摘掉放到栈中
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    if (stack.isEmpty())
        return null;
    ListNode node = stack.pop();
    ListNode dummy = node;
    //栈中的结点全部出栈，然后重新连成一个新的链表
    while (!stack.isEmpty()) {
        ListNode tempNode = stack.pop();
        node.next = tempNode;
        node = node.next;
    }
    //最后一个结点就是反转前的头结点，一定要让他的next
    //等于空，否则会构成环
    node.next = null;
    return dummy;
}

方法：递归

分析

因为效率问题，这里不做过多阐述

代码

public ListNode reverseList(ListNode head) {
    return reverseListInt(head, null);
}

private ListNode reverseListInt(ListNode head, ListNode newHead) {
    if (head == null)
        return newHead;
    ListNode next = head.next;
    head.next = newHead;
    return reverseListInt(next, head);
}