详解反转链表_链表反转

LeetCode链接

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

情况一：头结点为空

 情况二：链表只有一个节点

 情况三：链表多于1个节点。

 思路：让当前节点指向前一个节点。

如何才能做到当前节点指向前一个节点呢？

【第一步】定义一个为null的pre指针和cur指针指向头节点

 【第二步】让当前指针cur指向前一个指针pre；然后pre 移动到cur ，cur 移动到cur.next

temp 变量的定义就是方便cur 移动到cur.next 

 【第三步】循环移动使得链表反转，直到cur = null 最后返回pre

main 函数中链表的构建请参考：

一文读懂移除链表元素_abc123mma的博客-CSDN博客

反转前后结果如下：

 

【代码实现】

public class ReverseList {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        System.out.println("=========反转前=========");
        print(node1);
        ListNode node = reverse(node1);
        System.out.println("=========反转后=========");
        print(node);
 
 
    }
    // 采用双指针法
    public static ListNode reverseList(ListNode head) {
    // 如果链表为null 直接返回null
        if (head == null) {
            return null;
        }
    // 如果链表只有一个节点，直接返回头节点
        if (head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

方法二采用递归方式！

public static ListNode reverseList2(ListNode pre, ListNode cur) {
        if (cur == null) {
            return pre;
        }
        ListNode temp = cur.next;
        cur.next = pre;
        return reverseList2(cur,temp);
    }
    public static ListNode reverse(ListNode head) {
        return reverseList2(null,head);
    }