第一题 合并两个有序链表
题目信息
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路
这是数据结构中对于链表一道很经典的例题
因为两个链表都为升序链表，比拟两个链表的头部元素，并将小的数字退出到返回链表，遍历完一个链表后，再将另一链表的残余元素退出即可。
代码
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { head := &ListNode{} cur := head for l1 != nil || l2 != nil { if l1 != nil && l2 != nil { if l1.Val < l2.Val { cur.Next = l1 l1 = l1.Next } else { cur.Next = l2 l2 = l2.Next } cur = cur.Next } else if l1 != nil { cur.Next = l1 break } else { cur.Next = l2 break } } return head.Next}复杂度剖析
工夫复杂度：O(n+m)，其中 n 和 m 别离为两个链表的长度。
空间复杂度：O(1)。咱们只须要常数的空间寄存head和cur两个指针
第二题 回文链表
题目信息
解题思路
1.另辟蹊径的办法
2.快慢指针将链表分为两局部，再将其比拟
显然，快慢指针的办法更酷。对于无法访问前一节点的单向链表来说，快慢指针几乎是神器。
代码
数组
func isPalindrome(head *ListNode) bool { vals := []int{} for ; head != nil; head = head.Next { vals = append(vals, head.Val) } n := len(vals) for i, v := range vals[:n/2] { if v != vals[n-1-i] { return false } } return true}作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。快慢指针
func reverseList(head *ListNode) *ListNode { var prev, cur *ListNode = nil, head for cur != nil { nextTmp := cur.Next cur.Next = prev prev = cur cur = nextTmp } return prev}func endOfFirstHalf(head *ListNode) *ListNode { fast := head slow := head for fast.Next != nil && fast.Next.Next != nil { fast = fast.Next.Next slow = slow.Next } return slow}func isPalindrome(head *ListNode) bool { if head == nil { return true } // 找到前半部分链表的尾节点并反转后半局部链表 firstHalfEnd := endOfFirstHalf(head) secondHalfStart := reverseList(firstHalfEnd.Next) // 判断是否回文 p1 := head p2 := secondHalfStart result := true for result && p2 != nil { if p1.Val != p2.Val { result = false } p1 = p1.Next p2 = p2.Next } // 还原链表并返回后果 firstHalfEnd.Next = reverseList(secondHalfStart) return result}作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。复杂度剖析
工夫复杂度：O(n)，其中 n 指的是链表的大小。
空间复杂度：O(1)。咱们只会批改本来链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)。