关于golang:golangleetcode初级合并两个有序链表回文链表

第一题 合并两个有序链表

题目信息

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路

这是数据结构中对于链表一道很经典的例题
因为两个链表都为升序链表，比拟两个链表的头部元素，并将小的数字退出到返回链表，遍历完一个链表后，再将另一链表的残余元素退出即可。

代码

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