206.反转链表.md

206. 反转链表

url

题目

反转一个单链表。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

方法

两种方法：

• 尾递归
• 迭代头插：双指针分别是pre和cur，中间有个临时节点next
• 画画图就明白了

code

js

// 尾递归
let reverseList1 = head => {
    return reverse(null, head);
};
let reverse = (pre, cur) => {
    if (cur == null) return pre;
    let next = cur.next;
    cur.next = pre;
    return reverse(cur, next);
};
// 迭代头插
let reverseList = head => {
    let pre = null, cur = head;
    while (cur != null) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
};

go

// 尾递归
func reverseList1(head *ListNode) *ListNode {
	var reverse func (pre, cur *ListNode) *ListNode
	reverse = func (pre, cur *ListNode) *ListNode {
		if cur == nil {
		return pre
	}
		next := cur.Next
		cur.Next = pre
		return reverse(cur, next)
	}
	return reverse(nil, head)
}
// 迭代头插
func reverseList(head *ListNode) *ListNode {
	// 头插
	var pre *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

java

class Solution {
    public ListNode reverseList(ListNode head) {
        // 尾递归
        return reverse(null, head);
    }
    private ListNode reverse(ListNode pre, ListNode cur) {
        if (cur == null) return pre;
        ListNode next = cur.next;
        cur.next = pre;
        return reverse(cur, next);
    }
}
// 迭代头插法
class Solution {
    public ListNode reverseList(ListNode head) {
        // 头插
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}