反转链表

来源： JZ15-牛客网-反转链表

描述

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

示例1

1
2

输入：{1,2,3}
返回值：[3,2,1]

思路

假设我们现在正在对结点v进行反转操作，即原来结点u的next域指向v（图中已经调整完毕，现在指向前一个结点），v的next域指向w。

现在要做的是将v的next域指向u。从图中我们可以看出，当把v的next指针指向u的同时，原先指向的w就已经无法被正常的访问到了，为了避免“断链”，我们必须在指针更改指向之前，保存修改结点的下一结点。

同时我们也必须存储上一个结点，因为next域即将修改指向该结点。因此定义三个指针，分别指向当前遍历的结点，前一个结点和后一个结点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 定义链表结构
type ListNode struct {
	Val  int
	Next *ListNode
}

// 打印链表
func (l *ListNode) readLink() {
	var result []int
	for l != nil {
		result = append(result, l.Val)
		l = l.Next
	}
	fmt.Println(result)
}

ps: my ugly code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode  // nil
    cur := head
    for cur != nil{
        pNext := cur.Next // pNext保存w节点
        cur.Next = pre // 当前节点的后继指向pre
        pre = cur  // pre指针指针后移
        cur = pNext  // 当前指针也逐渐后移
    }
    return pre
}

复杂度分析：

时间复杂度：O(n)，其中 nn 是链表的长度。需要遍历链表一次。

空间复杂度：O(1)

高手解法与赏析

1628163092560

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

/*
方法二： 递归的一个思路
*/
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

复杂度分析：

时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。