1.1. 题目

1.1.1. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

1.1.2. 题解:

• 反转链表就是把之前链表的结果倒转过来,没啥不能理解的吧

1.1.3. 思路:

按照进阶要求,都解一遍试试

• 迭代

  • 迭代其实非常简单,因为没有要求不能重新定义一个链表,所以我们完全可以新定义一个链表,遍历当前链表,每遍历一个,就往新链表的前面插一个
  • 注意第一个的next是指向nil

• 递归

  • 我对递归用的特别少,所以花了我不少时间(大半天),最后还是没解出来,看了题解才解出来的
  • 如果是平常,可以定义一个全局变量,然后递归得倒序的链表,不过在 leetcode里 过不了的,因为全局可能会返回上一次的结果
  • 题解的思路是
    • 假如我们递归的是 1,2,3,4,5
    • 递归走到最里面,发现next == nil,这时返回 head ,也就是5
    • 递归回到了倒数第二层, 这时候是 4 -> 5 -> nil ,换成 4 -> 5 -> 4 ,因为4是指向5的,所以 这时候是 4 -> 5 -> 4 -> 5 ... 无限下去了
    • 这时候 应该把之前的断掉, 4-> 5 换成 4 -> nil ,就变成了 4 , 5 -> 4, 返回的一直都是 最里面的
    • 递归回到了倒数第三层, 这时候 3 -> 4 -> nil , 换成 3 -> 4 -> 3, 因为 3是指向4的,所以 这时候是 3 -> 4 -> 3 -> 4 ... 无限下去了
    • 这时候 应该把之前的断掉, 3 -> 4 换成 3 -> nil, 就变成了 3, 4 -> 3,
    • 一直递归返回下去
    • 多想想.. 确实有点难理解!

1.1.4. 代码:

 type ListNode struct {
      Val int
      Next *ListNode
 }
 // 递归
 func reverseList(head *ListNode) *ListNode {
     if head == nil || head.Next == nil {
         return head
     }
     s := reverseList(head.Next)
     head.Next.Next = head
     head.Next = nil
     return s
 }
 // 迭代(遍历)
 func reverseList2(head *ListNode) *ListNode {
     if head == nil || head.Next == nil  {
         return head
     }
     lastNode := &ListNode{
         Val: head.Val,
         Next: nil,
     }
     for head.Next != nil {
         head = head.Next
         newNode := &ListNode{
             Val: head.Val,
             Next:lastNode,
         }
         lastNode = newNode
     }
     return lastNode
 }

github代码