第一周，链表、栈、队列

第一周，链表、栈、队列

206. 反转链表

方法一：

双指针法：

• 定义两个指针：pre 和 cur
• 每次让 pre 的 next 指向 cur，实现一次局部反转
• 局部反转完成之后，pre 和 cur 同时往前移动一个位置
• 循环上述过程，直至 pre 到达链表尾部

class Solution {
	public ListNode reverseList(ListNode head) {
    	ListNode cur = null;
        ListNode pre = head;
        while (pre != null) {
        	ListNode t = pre.next;
            pre.next = cur;
            cur = pre;
            pre = t;
        }
        return cur;
    }
}

方法二

• 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret
• 此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前结点。
• 同时让当前结点的 next 指针指向 null，从而实现从链表尾部开始的局部反转
• 当递归函数全部出栈后，链表反转完成。

class Soulution {
	public ListNode reverseList(ListNode head) {
    	if (head == null || head.next == null) {
        	return head;
        }

        // 当 head.next为空时返回最后一个结点
        ListNode ret = reverseList(head.next);
        // head 此时是反转前和反转后的中间结点，将反转后的结点的next指向head
        // 然后将head指向null
        head.next.next = head;
        head.next = null;
        return ret;
    }
}

双指针优化：

• 原链表的头结点就是反转之后的尾结点，使用 head 标记
• 定义指针 cur，初始化 head
• 每次都让head下一个结点 next 指向 cur，实现一次局部反转
• 局部反转完成之后，cur 和 head 的 next 指针同时往前移动一个位置
• 循环上述过程，直至 cur 到达链表的最后一个结点

class Soulution {
	public ListNode reverseList(ListNode head) {
    	if (head == null) {
        	return null;
        }
        ListNode cur = head;
        while (head.next != null) {
        	ListNode t = head.next.next;
            head.next.next = cur;
            cur = head.next;
            head.next = t;
        }
        return cur;
    }
}