LeetCode reverse-linked-list

2020-12-26

https://leetcode-cn.com/problems/reverse-linked-list/

在更新链表指向前, 先保存原 next 信息.

迭代法

Golang

package main

import "fmt"

func main() {
	//1->1->2->3
	list := &ListNode{Val: 1, Next: &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3}}}}

	res := reverseList(list)
	fmt.Println(res)
}

type ListNode struct {
	Val  int
	Next *ListNode
}

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

	nextPtr := head.Next
	head.Next = nil
	for nextPtr != nil {
		nextNextPtr := nextPtr.Next
		nextPtr.Next = head

		head = nextPtr
		nextPtr = nextNextPtr

		if nextNextPtr != nil {
			nextNextPtr = nextNextPtr.Next
		}
	}
	return head
}

递归法

假设原链表: 1->2->3->4->nil

重点在处理最后的最小子问题. 经过递归之后, 划分子问题, 到最后一步: 1->2<-3<-4, 此时 head 为 1.

Golang

package main

import "fmt"

func main() {
	//1->2->3
	list := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3}}}

	res := reverseList(list)
	fmt.Println(res)
}

type ListNode struct {
	Val  int
	Next *ListNode
}

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
}