24-反转链表
大约 3 分钟
输入一个链表，反转链表后，输出新链表的表头。
循环解法
通常感觉各种操作链表比较乱，其实理清了也还好。
如果顺序遍历链表，可以使用三个节点。
tmp节点表示当前反转后的链表头
pre节点表示前一个节点，用于修改当前节点的next指针
head节点表示当前正在访问的节点
如下图链表所示，此时是初态。
我们首先将tmp节点指向head节点，然后将head节点指向下一个节点，然后将tmp的next指向pre节点，因为是第一个节点，pre是null，然后将pre指向tmp节点，也就是下一次循环对应的前一个节点。
第二次循环和上面的执行过程一样，将tmp前移一节点，然后head也前移一节点，tmp的next指向上一轮的pre节点，也就是A节点，然后更新pre为当前的tmp节点。
第三次循环同理，最后head为null，循环结束。
代码如下。
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
ListNode tmp = null;
ListNode pre = null;
while (head != null) {
tmp = head;
head = head.next;
tmp.next = pre;
pre = tmp;
}
return tmp;
}
递归解法
怎么解决这道题呢？解决这道题的第一步就是解决这道题。
迭代是人 递归是神
首先假设我们有一个方法，该方法入参是一个链表头结点，返回反转该链表后的头结点。
public ListNode ReverseListCore(ListNode head) {
//暂且将该方法作为一个黑盒
}
我们拿第一个node举例，代码应该是这样的：
ListNode pNode = ReverseListCore(head.next);//反转以head的后续结点为头结点的链表得到新头结点
head.next.next = head; //将第一个节点的后续结点指向第一个结点
head.next = null;//将第一个结点的后续结点置为null
return pNode;
那么第一个结点是这样，后续结点呢？其实都是一样的。
public ListNode ReverseList(ListNode head) {
ListNode pNode = ReverseListCore(head.next);
head.next.next = head;
head.next = null;
return pNode;
}
此时我们有一个惊人的发现，ReverseList和ReverseCore是一样的！
一样就可以合并。
public ListNode ReverseList(ListNode head) {
ListNode pNode = ReverseList(head.next);
head.next.next = head;
head.next = null;
return pNode;
}
此时需要注意递归的结束条件和head==null这种情况。
public static ListNode ReverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pNode = ReverseList(head.next);
head.next.next = head;
head.next = null;
return pNode;
}
递归其实就是栈。
- 结束条件
- 将大问题变成小问题或者变成前一个问题
- 如何将结果进行合并
程序上的套路大概是:
A(){
结束条件;
递归前处理(可能有);
A();
递归后处理(可能有);
return ;
}
递归在嵌套层次太深时会导致栈溢出，不过递归对于我们思考问题很有帮助。