leetcode 单链表的各种算法

1 递归实现：合并两个有序的单链表

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1){
            return l2;
        } 
        if(!l2){
            return l1;
        }
        if (l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }else{
             l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
}

2 递归实现：单链表逆序存入vector

vector<int> reversePrint(ListNode* head) {
        if(!head){
            return {};
        }
        vector<int> vec = reversePrint(head->next);
        vec.push_back(head->val);
        return vec; //std::move()
    }

3 循环实现：快慢指针找到单链表中间位置

876. 链表的中间结点

ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        //判断连续2个指针不为 NULL
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

4 深度拷贝一个指针

面试题35. 复杂链表的复制

时间O(n)
空间O(1)
思路：在原有指针后面dup一个，然后设置random指针，最后分离两条链！
有点像DNA复制(不过DNA是双链结构)

Node* copyRandomList(Node* head) {
        if(head == NULL){
            return NULL;
        }
        Node* p = head;
        // copy at right side
        while(p != NULL){
           Node* copy = new Node(p->val);
           copy->next = p->next;
           p->next = copy;
           p = p->next->next;
        }
        // set up random ptr
        p = head;
        while(p != NULL){
            Node* copy = p->next;
            if(p->random) {
               copy->random = p->random->next; 
            }
            p = p->next->next;
        }
        //split into 2 list
        p = head;
        Node* copy_header = p->next;
        while(p){
             Node* copy = p->next;
             p->next = p->next->next;
             //move p to next
             p = p->next;
             if(p){
                 copy->next = p->next;
             }
        }
        return copy_header;
    }

5 递归删除链表中的一个元素

面试题18. 删除链表的节点

ListNode* deleteNode(ListNode* head, int val) {
        if(head == NULL){
            return NULL;
        }
        if(head->val == val){
            return head->next;
        }
        head->next = deleteNode(head->next, val);
        return head;
    }

6 递归实现：两个链表求和

面试题 02.05. 链表求和

 ListNode* addLists(ListNode* l1, ListNode* l2){
        if(!l1){
            return l2;
        }
        if(!l2){
            return l1;
        }
        ListNode* head = new ListNode(l1->val + l2->val);
        head->next = addLists(l1->next, l2->next);
        return head;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = addLists(l1, l2);
        adjust(head);
        return head;
    }
    void adjust(ListNode* head){
        int surplus = 0;
        while(head){
            int sum = head->val + surplus;
            head->val = sum % 10;
            surplus = sum / 10;
            if(head->next == NULL){
                break;
            }
            head = head->next;
        }
        if(surplus){
            head->next = new ListNode(surplus);
        }
    }

7递归查找单链表第k个元素

面试题22. 链表中倒数第k个节点

ListNode* solve(ListNode* head, int k, int& count){
        if(head == NULL || head->next == NULL){
            count = 1; 
            return (k==1?head:NULL); 
        }
        ListNode* kth = solve(head->next,k, count);
        if(++count == k) {
            return head;
        }
        return  kth;
    }
    ListNode* getKthFromEnd(ListNode* head, int k) {
        int count = 0;
        return solve(head,k,count);
    }

8 判断两个单链表 有没有交点

面试题 02.07. 链表相交
这个题目还说蛮有技巧性的。
采用双指针，走两遍的方法。

/**双指针，走两遍
    * 没有交点：两个指针都同时到达对方链表的尾部 NULL
    * 有交点: 两个指针同时到达交点处。
    */
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pa = headA;
        ListNode *pb = headB; 
        while(pa != pb){
            if(pa){
                pa =  pa->next;
            }else {
                pa = headB;
            }
            if(pb){
                pb =  pb->next;
            }else {
                pb = headA;
            }
        }
        return pa;
    }