leetcode一步解决链表反转问题

反转链表

题目描述：

 

看到链表反转，小伙伴们心中不禁会想，这种题我做过无数次了， 太简单了，但是大家有没有把解法研究透彻呢？今天我就来给大家讲讲我理解的几种链表反转方法(我理解的哈哈哈)

注：大家学习的时候可以跟着画图过一遍，方便理解

1、利用栈

思路：利用栈就是一个很普遍的方法了，就是利用栈先入后出的特性，完美符合链表反转所需要的条件，在这里我们直接上代码：

public ListNode ReverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode temp = head;
        //1、入栈
        while (temp != null){
            stack.push(temp);
            temp = temp.next;
        }
        ListNode result = stack.pop();
        ListNode listNode = result;
        //2、出栈
        while (stack.size() != 0){
            ListNode pop = stack.pop();
            result.next = pop;
            result  = result.next;
        }
        result.next = null;
        return listNode;
    }

时间复杂度：O(n)

空间复杂度：O(n) 

2、从头节点开始连接

思路：我们直接采用从头到尾，依次连接到新的辅助节点后面，最后再返回辅助接点.next

这个时候我们有两种情况：

1）、一种是固定好头节点，不断插入到辅助接点后面

 如图，不断插入进去，直到最后一个节点也插入到辅助节点后面

很好理解，我们来看看代码：

public ListNode reverseList(ListNode head){
        ListNode pre = null;
        ListNode temp = head;
        ListNode next;
        while (temp != null) {
            next = temp.next;
            temp.next = pre;
            pre = temp;
            temp = next;
        }
        return result;
    }

 2）、先定义一个尾部节点

 把原来链表的头节点不断连接到新的链表上,代码如下：

public ListNode reverseList3(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode result = null;
        ListNode cur = head;
        ListNode next;
        while (cur != null){
            next = cur.next;
            cur.next = result;
            result = cur;
            cur = next;
        }
        return result;
    }

 时间复杂度：O(n)

 空间复杂度：O(1)

3、在原链表中进行反转

思路：既然我们可以把元素放到新的头结点上， 那我们一定会想在原来的链表上能不能进行反转呢？答案是可以，我们不需要一次反转成功,一次一次来，给大家画个图方便理解

这是第一次反转，每一步反转一次，直到反转完成 ，我们看看代码：

public ListNode reverseList2(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode pre = new ListNode(-1);
        pre.next = head; //前序节点
        ListNode cur = head;
        int len = 0; //链表总长度
        ListNode temp = head;
        while (temp != null){
            len++;
            temp = temp.next;
        }
        for (int j = 1; j < len; j++) {
            temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return pre.next;
    }

时间复杂度：O(n)

空间复杂度：O(1)

总结：链表反转虽然是一个十分老套的题目，但是绝对值得大家学习透彻，学会这几种方法，大家保证以后遇到有关链表反转的题目，直接拿捏~