leetcodetop100 (22) 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

简单的用一个动态数组Arraylist记录，然后倒序遍历赋值给一个新的链表，这种空间复杂度是o(n),估计需要优化。

采用双指针；

我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。

；

package TOP11_20;// 反转链表
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
public class Top21 {public class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}}public static ListNode reverseList(ListNode head) {//采用双指针ListNode pre = null;ListNode cur = head;// 有点难以理解 可以采用画图方式理解，第二个指针 cur 指向 head，然后不断遍历 cur。//每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。//都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。while (cur!=null){ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}

harryptter / LeetcodeTop100 · GitCode