单链表反转

反转单链表是一个很常见的问题

迭代法

最直观的方法就是遍历链表的同时将其反转

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)。