206. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
思路
双指针法：
1 cur指向要插入的节点
2 pre指向cur前面的节点
3 head.next指向cur.next；cur.next指向pre
4 继续挪动pre和cur，pre指向cur，cur指向head.next
代码
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null){
return head;
}
//cur指向要插入到前面的节点，插入后cur指向head的next
//pre指向被cur插入到前面的节点，被插入后再指向cur
//head每次指向cur的next节点，即下一次的cur，最终变尾结点
ListNode pre = head;
ListNode cur = pre.next;
while (cur != null){
head.next = cur.next;
cur.next = pre;
pre = cur;
cur = head.next;
}
return pre;
}
}