关于golang:golangleetcode中级两数相加奇偶链表

第一题 两数相加

题目

解题思路

具体代码

func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {
    var tail *ListNode
    carry := 0
    for l1 != nil || l2 != nil {
        n1, n2 := 0, 0
        if l1 != nil {
            n1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            n2 = l2.Val
            l2 = l2.Next
        }
        sum := n1 + n2 + carry
        sum, carry = sum%10, sum/10
        if head == nil {head = &ListNode{Val: sum}
            tail = head
        } else {tail.Next = &ListNode{Val: sum}
            tail = tail.Next
        }
    }
    // 如果两数相加之后产生了进位，则减少一个新的节点
    if carry > 0 {tail.Next = &ListNode{Val: carry}
    }
    return
}

复杂度剖析

工夫复杂度：O(max(m,n))，其中 m 和 n 别离为两个链表的长度。咱们要遍历两个链表的全副地位，而解决每个地位只须要 O(1) 的工夫。

空间复杂度：O(1)。留神返回值不计入空间复杂度。

第二题 奇偶链表

题目

解题思路

代码

func oddEvenList(head *ListNode) *ListNode {
    // 如果链表为空，则间接返回链表。if head == nil {return head}
    // 第一个奇偶节点  odd 奇数的  even 偶数的
    evenHead := head.Next
    odd := head
    even := evenHead
    // 将原链表别离连贯到奇偶链表
    for even != nil && even.Next != nil {
        odd.Next = even.Next
        odd = odd.Next
        even.Next = odd.Next
        even = even.Next
    }
    // 偶链表加到奇链表后
    odd.Next = evenHead
    return head
}

复杂度剖析

工夫复杂度：O(n)，其中 n 是链表的节点数。须要遍历链表中的每个节点，并更新指针。

空间复杂度：O(1)。只须要保护无限的指针。