免费微网站建设宣传软文

反转一个单链表

题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路

需要虚拟节点么？
答：不需要，因为没有删除节点，只是改变了节点的指向。
遍历之后，如果找到之前的节点？
答：双指针。我们利用双指针来标识前一个节点。
首先我们为什么需要前一个节点？
答：因为当前节点的下一个节点需要指向前一个节点。所以需要下一个节点。
给兄弟们上一个动图，就明白一切了。

代码

//class ListNode{
//    private int val;
//    private ListNode next;
//    ListNode(int val){
//        this.val = val;
//    }
//    ListNode(int val,ListNode next){
//        this.val = val;
//        this.next = next;
//    }
//}
public class reverseTreeTest {//1. 双指针法public ListNode reverserTree(ListNode head) {ListNode prev = null;ListNode cur = head;ListNode temp;while (cur != null) {//步骤一：记录下下一个节点temp = cur.next;//步骤二：当前节点指向前一个节点cur.next = prev;//步骤三：之前的节点变成cur节点（因为1->null 之后，当遍历2的时候，需要 2->prev（1->null）,如果这里不赋值，会变成2->null）prev = cur;//步骤四：当前节点变成下一个节点cur = temp;}return prev;}}

总结

双指针法在解决链表的时候，是一种常见的算法。比如后面的链表中寻找环，也是利用双指针（快慢指针）相遇来判断是否有环。
这个题目，唯一需要注意的是：虽然只有4行代码。但是你得理解每行代码的意义。实在不行，自己手动画一画，也就理解了。如果还是理解不了，先记着吧，后面熟能生巧。嘻嘻。