Java反转链表（递归和迭代两种方式）_java 反转链表

LeetCode

• https://leetcode-cn.com/problems/reverse-linked-list/
• 两种解法的视频讲解

递归

• 使用递归的3个条件
  1. 大问题可以拆解成两个子问题
  2. 子问题的求解方式和大问题一样
  3. 存在最小子问题

    public ListNode reverseList(ListNode head) {
        //最小子问题，结束
        if (head == null || head.next == null) return head;
        //递的过程，一次次拆解问题
        ListNode newHead = reverseList(head.next);
        //归的过程，反转
        head.next.next = head;
        head.next = null;
        return newHead;
    }
1
2
3
4
5
6
7
8
9
10

迭代

    public static ListNode reverseListIterative(ListNode head) {
        ListNode prev = null; //前指针节点
        ListNode curr = head; //当前指针节点
        ListNode next;
        //每次循环，都将当前节点指向它前面的节点
        //然后当前节点和前节点后移
        while (curr != null) {
        	//临时节点，暂存当前节点的下一节点，用于后移
        	//因为接下来curr.next进行赋值后将会断链
            next= curr.next; 
            //将当前节点指向它前面的节点
            curr.next = prev; 
            //前指针后移
            prev = curr; 
            //当前指针后移
            curr = next; 
        }
        return prev;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

参考资料

• https://www.cnblogs.com/keeya/p/9218352.html