Leetcode206:反转链表

一、题目

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

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

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

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

二、题解

1.头插法

构造一个新链表，从旧链表中取出节点，一个个插入到新链表的头部，最后就逆序了。

image.png

public static Node reverseList1(Node head) {
    //新链表的头节点
    Node node = null;
    //遍历旧链表
    while (head != null) {
        //每次都创建一个新节点，放在新链表的头部（当前链表的next是之前的node）
        node = new Node(head.value, node);
        //让旧链表的头指针往下移动一位
        head = head.next;
    }
    return node;
}

2.双指针

• 1.因为要改变指针的方向，会丢失掉原本next的指针，所以让next元素先暂存起来：ListNode temp = head.next;
• 2.改变cur指针的指向（head指针）head.next = pre;
• 3.让pre和cur同时向后移动 pre = head; head = temp;
• 4.当cur指向到null时，遍历完毕 head!=null
  image.png

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while(head!=null){
            //把当前节点的后一个节点暂存到temp
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}

3.递归

通过递归调用每次让头指针往后移，即相当于执行了head = head.next
在递归内部的操作把指针的指向改变，为了防止循环引用，在改变完当前节点的指向后，还要把前一个节点的指针指为空。

image.png

public static Node reverseList(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    //返回最后的节点
    Node node = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return node;
}