LeetCode 递归模块Ⅱ 2020年8月30日
LeetCode
0 条评论

1. 合并链表

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

示例：

输入：1->2->4, 1->3->4

输出：1->1->2->3->4->4

原code：

class Solution {
public:
    ListNode* find(ListNode* head,int temp)
    {
        ListNode* current=NULL;
        while(head!=NULL&&head->val<temp)
        {
            current=head;
            head=head->next;
        }
        return current;
    }//查询位置函数
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        ListNode* now=l1;
        while(l2!=NULL)
        {
            ListNode* p=l2;
            ListNode* place=find(now,l2->val);
            l2=l2->next;
            if(place==NULL)//链表头
            {
                p->next=l1;
                now=p;
                l1=p;
                continue;
            }
            if(place->next==NULL)//链表尾
            {
                place->next=p;
                p->next=NULL;
                now=place;
                continue;
            }
            p->next=place->next;//链表中
            place->next=p;
            now=place;
        }
        return l1;
    }
};

时间复杂度：O(m+n)

力扣题解思路;

1.简单的递归

class Solution:

    def mergeTwoLists(self, l1, l2):

        if l1 is None:

            return l2

        elif l2 is None:

            return l1

        elif l1.val < l2.val:

            l1.next = self.mergeTwoLists(l1.next, l2)

            return l1

        else:

            l2.next = self.mergeTwoLists(l1, l2.next)

            return l2

时空都是O(m+n)//不是尾递归，会有累计的递归栈

2. 迭代实现

用虚节点假装构建新链表

class Solution {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode prehead = new ListNode(-1);//虚节点

        ListNode prev = prehead;

        while (l1 != null && l2 != null) {

            if (l1.val <= l2.val) {

                prev.next = l1;

                l1 = l1.next;//给虚链表连接已有节点

            } else {

                prev.next = l2;

                l2 = l2.next;

            }

            prev = prev.next;

        }

        return prehead.next;

    }

}

 

2. 第k个语法符号

思路，位运算和递归的运用

巧妙的点：非pow(2,n)求2^n，而是借助1<<n从而快速算出2^n

取非也可不用！而是^1，位运算效率能高出不少

原题链接

使用位运算修改过的代码：

class Solution {
public:
    int kthGrammar(int N, int K) 
    {
        if(N==1)
        {
           return 0;
        }
        
        if(K<=1<<N–2)
            return kthGrammar(N–1,K);
        else
            return kthGrammar(N–1,K-(1<<N–2))^1;
        
    }
};