单链表反转
单链表反转
反转单链表是一个很常见的问题
迭代法
最直观的方法就是遍历链表的同时将其反转
package main
import . "nc_tools"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
func ReverseList(head *ListNode) *ListNode {
// write code here
if head == nil {
return nil
}
var perNode, curNode *ListNode
perNode = head
curNode = head.Next
head.Next = nil
for curNode != nil {
nextNode := curNode.Next
curNode.Next = perNode
perNode = curNode
curNode = nextNode
}
return perNode
}
头插法
头插法就是遍历原链表的同时，将节点添加到新链表的头部
package main
import . "nc_tools"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
func ReverseList(head *ListNode) *ListNode {
// write code here
if head == nil {
return nil
}
newHead := &ListNode{Val: head.Val, Next:nil}
curNode := head.Next
for curNode != nil {
newHead = &ListNode{Val: curNode.Val, Next: newHead}
curNode = curNode.Next
}
return newHead
}
递归法
利用递归的思路来解决这个问题
package main
import . "nc_tools"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
func ReverseList(head *ListNode) *ListNode {
// write code here
if head == nil || head.Next == nil{
return head
}
newHead := ReverseList(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}
总结
迭代法最直观，时间复杂度为O(n)，空间复杂度为O(1)。但是在编写代码时容易出错。
头插法通过逆向思维，将链表反转，时间复杂度O(n)，空间复杂度O(n)。
递归法代码简洁，时间复杂度O(n)，空间复杂度O(n)。