递归解法

示意图

image.png

代码

 // 递归
    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;
    }

这个代码第一个难点在于返回的newHead是等于最后一个节点的,但是此时,当前的这个函数head指向的倒数第二个节点。

示意图

image.png

第二难点在于重现构建链表指向的关系

image.png

此时的链表的示意图

image.png

return newHead之后该当前函数出栈,此时head指向的是3

图示

image.png

image.png

重现构建链表的指向关系

image.png

此时的示意图如下

image.png

以此类推,每一个函数出栈后都会重新构建链表的指向关系,然后返回指向newhead(指向的是5)
因此将链表反转过来了
1<-2<-3<-4<-5
源代码:

public class _206_反转链表 {
    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
      }
  }
  // 递归
    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;
    }
}

迭代解法

双指针的解法,先设置一个当前指针current=head,一个newHead=null的指针 。
第一轮迭代图示:

image.png

迭代的一个难点在head.next=newHead是在下一个轮循环完成的。 current.next = newHead; 这句代码在下路迭代中重新构建了链表的指向关系。
下一轮图示：

image.png

以此类推可将链表反转
源码：

class Solution {
   public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode current = head;
        ListNode newHead = null;
        while(current != null) {
            ListNode temp = current.next;
            current.next = newHead;
            newHead = current;
            current = temp;
        }
        return newHead;
    }
}