网站建设最好的公司百度联盟项目看广告挣钱

反转链表

Leetcode题目链接

题意：翻转一个单链表

🌰:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

在链表本身进行反转即可，不用重新定义链表，这同时浪费时间和空间。

需要采用哑节点吗？
不需要的，如果使用了哑节点还会造成报错。
如果给原链表添加哑节点：
dummy ->1->2->3->4->5->NULL
那么我们反转后就变成了：
5->4->3->2->1->dummy
这是不合理的，所以不使用哑节点。
还有一个问题，循环判断的条件是什么？
在该问题中，当链表被遍历到末尾后，程序便结束。
所以需要一个条件来确定链表是否已经被遍历到末尾。
代码如下：

class Solution{public ListNode reverseList(ListNode head){ListNode pre = null;ListNode cur = head;ListNode next = null;while(cur != null){next = cur.next;cur.next = pre;pre = cur;cur = next;}//注意，反转链表后，原来的末尾成为现在的头return pre; }
}

递归方法：

// 递归 
// 递归的核心思路和双指针是一样的。
class Solution {public ListNode reverseList(ListNode head) {return reverse(null, head);}private ListNode reverse(ListNode prev, ListNode cur) {// 注意递归出来的条件，当前节点为null，表明已经遍历完成if (cur == null) {return prev;}ListNode temp = null;temp = cur.next;// 先保存下一个节点cur.next = prev;// 反转// 更新prev、cur位置// prev = cur;// cur = temp;return reverse(cur, temp);}
}