关于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)。只须要保护无限的指针。