输入一个链表,反转链表后,输出新链表的表头。

package linkedlist;

import common.ListNode;

public class 反转链表 {
    /**
     * 自想1:
     * 需要把cur.next先记下来再改变指针,注意边界条件
     * 时间复杂度O(n),空间复杂度O(1)
     * */
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = null, cur = head, pos;
        // 进入循环的最后一个数:cur为列表的最后一个数,把cur的next指针指向pre
        while (cur != null) {
            pos = cur.next;
            cur.next = pre;
            pre = cur;
            cur = pos;
        }
        // 但是退出循环的时候cur == null,最后返回的是pre
        return pre;
    }
}

results matching ""

    No results matching ""