链表反转面试题

链表反转-基础篇
题目
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
考察要点

• 链表的熟悉程度
• 迭代法和递归法两种实现思路

• 迭代法：

  • 优点：效率高，运行时间只随循环的增加而增加；无额外开销；
  • 缺点：代码难理解；代码不如递归代码简洁；

• 递归法：

  • 优点：用有限的循环语句实现无限集合；代码易读；大问题转化成小问题，减少代码量；
  • 缺点：递归不断调用函数，浪费空间；容易造成堆栈溢出。
• 复杂度：时间复杂度O(N)，空间复杂度O(1)

解法1：迭代法
通过双指针，遍历 head 指针，通过中间变量，逐步指向新的 head 节点，完成链表反转

type ListNode struct {
   Val  int
   Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
   if head == nil {
      return nil
   }
   var newHead *ListNode
   for head != nil {
      node := head.Next
      head.Next = newHead
      newHead = head
      head = node
   }
   return newHead
}

解法2：递归法
整体思路是递归到最后一个节点，这个节点就是链表反转后的头节点，这里记作 ret，最终只需要返回这个 ret 指针即可，剩余的都是对中间数据进行指针反转。

type ListNode struct {
   Val  int
   Next *ListNode
}

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

   ret := reverseList(head.Next)
   head.Next.Next = head
   head.Next = nil
   return ret
}

链表反转-进阶篇
题目
反转从位置 m 到 n 的链表. 请使用一趟扫描完成反转.
示例：
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
考察要点

• m和n之间的反转与基础篇一样
• 在m的边界处理，m-1的next指向n；m的next指向n+1

• 在n的边界处理，n的next指向n-1；
  解法1:迭代法

  func reverseBetween(head *ListNode, m int, n int) *ListNode {
    dummy := ListNode{Val: 0}
    dummy.Next = head
    node := &dummy
    for i := 1; i < m; i++ {
        node = node.Next
    }
    pre := node
    curr := node.Next
    tail := curr
    for i := m; i <= n; i++ {
        nxt := curr.Next
        curr.Next = pre
        pre = curr
        curr = nxt
    }
    tail.Next = curr
    node.Next = pre
    return dummy.Next 
  }

  解法2:递归法

  type ListNode struct {
   Val  int
   Next *ListNode
  }
  
  func rev(root *ListNode) *ListNode {
   if root == nil || root.Next == nil {
      return root
   }
  
   last := rev(root.Next)
   root.Next.Next = root
   root.Next = nil
  
   return last
  }
  func reverseBetween(head *ListNode, left int, right int) *ListNode {
   d := &ListNode{
      Val:  0,
      Next: head,
   }
   h := d
   tmp := head
  
   var leftNode *ListNode
   var rightNode *ListNode
   var prevNode *ListNode
   var nextNode *ListNode
   foundLeft := false
   foundRight := false
   count := 1
   _ = rightNode
   for tmp != nil {
      if foundLeft && foundRight {
         break
      }
  
      if count == left {
         leftNode = d.Next
         d.Next = nil
         prevNode = d
         foundLeft = true
      }
  
      if count == right {
         rightNode = tmp
         nextNode = tmp.Next
         tmp.Next = nil
         foundRight = true
      }
  
      count++
      d = tmp
      tmp = tmp.Next
   }
  
   last := rev(leftNode)
   prevNode.Next = last
   leftNode.Next = nextNode
   return h.Next
  }