链表反转

方法一:虚拟头结点

image (10)

当连接第一个元素时,dummy.next=null,因此,反转后的链表的第一个节点的next为null

需要三个指针,next,cur,以及ans

步骤:

1.先将next往后移动一位

2.将当前cur的下一个指向ans.next(cur为第一个时,ans.next=null)

3.ans.next指向cur

4.将cur后移一位

    ListNode ans = new ListNode(-1);
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = ans.next;
        ans.next = cur;
        cur = next;
    }
    return ans.next;
}

方法二:直接操作

也就是需要三个指针,一个指针指向下一个元素,一个指针指向前一个元素

步骤:

1.先将next移动到下一位

2.将cur当前元素下一个设置为前一个元素

3.pre前一个元素后移到cur

4.cur后移到next

image (9)

public ListNode reverseList(ListNode head ) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}