[数据结构与算法]1.反转链表

Java面试高频题（每日打卡）
LeetCode 206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

算法1 递归

思路：reverseList(head) 的作用是把所有由head指向的所有节点进行反转，可以把后面n - 1个结点看成一个整体，先进行反转得到tail 链表，再把第一个结点拼在tail链表的尾部，且第一个结点最后指向null

head.next.next = head;他的作用就是进行反转，

• 当 head == null || head.next == null 则回溯，即归。因为每次进行的是 reverseList(head.next)。然后再判断head == null || head.next == null ，比如head = [1,2,3,4,5]，4.next是5，而5.next为null，即不满足条件，则回溯，回溯后此时head指向4，一定要理解reverseList(head.next)中的head.next,是指向下一个的，所以回溯后head指向4，就明白了head.next.next就是指向5.next，因为head指向4，所以把head赋给head.next.next，，即完成5->4翻转，强烈不懂的建议画图

head.next = null,此时变成5->4->null

然后再进行回溯

   /**
     * Definition for singly-linked list.
     * 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) {
            if(head == null || head.next == null) 
                return head;
             ListNode tail = reverseList(head.next);//tail最终是指向最后一个节点，即翻转链表的开头
             head.next.next = head;
             head.next = null;
             return tail;   
        }

}

迭代(容易理解)

• 翻转即将所有节点的next指针指向前驱节点。
  由于是单链表，我们在迭代时不能直接找到前驱节点，所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的next指针前，不要忘记保存它的后继节点。
• 空间复杂度分析：遍历时只有3个额外变量，所以额外的空间复杂度是 O(1)。
• 时间复杂度分析：只遍历一次链表，时间复杂度是 O(n)。

    class Solution {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode a=head;
            ListNode b=head.next;
            while(b!=null){
                ListNode c=b.next;
                b.next=a;
                a=b;
                b=c;
            }
            head.next=null;
            return a;
        }
    }

2种代码效果相同，只是起点不一样

    class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }
    }