递归解法
示意图
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;
}
}
