206. 反转链表

206. 反转链表 #

题目地址 #

类似/相同题目: 剑指 Offer 24. 反转链表

解题思路 #

迭代法 #

TODO

递归法 #

TODO

具体实现 #

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}

	var (
		prev, next *ListNode
		curr       = head
	)

	for curr != nil {
		next = curr.Next
		curr.Next = prev
		// 下一个
		prev = curr
		curr = next
	}

	return prev
}

func main() {
	reverseList(&ListNode{
		Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}}})
}
package main

import (
	"fmt"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	// head == null:当第一次输入为 nil 的时候直接返回 nil,不进行递归操作。
	// head.next == null:返回链表的最后一个节点
	if head == nil || head.Next == nil {
		return head
	}

	newHead := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil

	return newHead
}

func main() {
	x := reverseList(&ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val:  4,
					Next: nil,
				},
			},
		},
	})
	fmt.Println(x)
}

参考 #