复杂度为O(n)的链表反转遍历方法笔记



详细图解过程(纯exl手打)。




Java版本:

public ListNode reverseList (ListNode head) {
    ListNode prev = null;//让prev指针指向null
    ListNode curr = head;//让当前指针指向head
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;//此时第一次执行,指向着null
        prev = curr;
        curr = next;
    }
    return prev;
}

JavaScript版:

function reverseList (head) {
    let prev = null;//any类型
    let curr = head;//any类型
    while (curr != null) {
        const next = curr.next;//强声明,值不可变
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}


其实定义的next算是一个临时变量,tmp。这个tmp会将curr的下一个节点临时保存起来。所以其实是:

class Solution {
    public ListNode reverseList(ListNode head) {
        //申请节点,pre和 cur,pre指向null
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while(cur!=null) {
            //记录当前节点的下一个节点
            tmp = cur.next;
            //然后将当前节点指向pre
            cur.next = pre;
            //pre和cur节点都前进一位
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}