Leetcode - 链表

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
    
        // 因为头结点没有前驱，因此特殊处理
        while(head && head->val == val){
            head = head->next;
        }
        
        // 如果值相等，节点前驱指向节点后继；如果不等，更新前驱；
        ListNode* pre = NULL;
        ListNode* p = head;
        while(p != NULL){
            if(p->val == val){
                pre->next = p->next;
            }else{
                pre = p;
            }
            
            p = p->next;
        }
        return head;
    }
};

class Solution {
public:
	/**
		大佬的解法，惊为天人；
		一路往下传，底部为真时修改head的指向，同时函数出栈，p回到上一p。太tm绝了
		缺陷是没能利用中点，这个算法相当于比了两遍
	*/
    bool check(ListNode** head, ListNode* p){
        if(p == NULL) return true;
        bool res = check(head, p->next);
        if((*head)->val != p->val) return false;
        *head =(*head)->next;
        return res;
    }
    
    bool isPalindrome(ListNode* head) {
        return check(&head, head);
    }
};

//另解，快慢指针找到中间节点，将后半部分逆置，然后顺序比较即可

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == NULL || head->next == NULL ) return head;
        head->next = deleteDuplicates(head->next);
        return head->val==head->next->val //如果下一个值等于下下个值
            ? head->next //下一个等于下下一个
            : head; //下一个等于下一个
    }
};

class Solution {
public:
    /**
    大佬的解法，惊为天人
    假设A有长度a+c，B有长度b+c
    再假设A先走完了a+c，则将A的触发点移动到B。同理如果B走完了b+c。移动到A
    那么无论c是多少，最终一定有 a+c+b+c = b+c+a+c
    也就是说AB一定会相遇
    时间复杂度为O(2a+2b)
    */
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL || headB == NULL )return NULL;
        ListNode* a = headA;
        ListNode* b = headB;
        
        while(a!=b) {
            a = (a == NULL ? headB : a->next);
            b = (b == NULL ? headA : b->next);
        }
        
        return a;
    }
};

//另解，求出A的长度a+c，求出B的长度b+c；假设a>b，移动a至a-b，则到达共同出发点

class Solution {
public:
    /**
         1     2   3    4    5
    pre head next
    
    head指向pre，然后挨个后移
    */
    ListNode* reverseList(ListNode* head) {
        if(!head) return NULL;
        ListNode* pre = NULL;
        while(head){
            ListNode* next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }        
        return pre;
    }
    
    
    // recursion version
   	/**
   	用栈来理解的话，相当于依次入栈直到倒数第二个节点，单独拿出最后一个节点，
   	然后开始出栈，令出栈元素的下一个节点反过来指向自己
   	*/
    ListNode* reverseList(ListNode* head) {
        if(head==NULL || (head->next == NULL))
            return head; //找到最后一个节点
        
        ListNode* last = reverseList(head->next);
        head->next->next = head; //让下一个的下一个指向自己， 到这里暂时形成一个环
        head->next = NULL; //下一个指向空，将环断开，符合链表结构
        return last; //最后一个节点未动，作为头结点返回
    }
};

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* p1 = head, *p2 = head;
        while(p2&&p2->next){
            p2 = p2->next->next;
            p1 = p1->next;
        }
        return p1;
    }
};

class Solution {
public:
    // recursion version
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        
        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
    
    //iterative version
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* ret = new ListNode();
        ListNode* p = ret;
        while(l1 && l2){
            ListNode** smaller = (l1->val < l2->val) ? &l1 : &l2;
            p->next = *smaller;
            p = p->next;
            *smaller = (*smaller)->next; 
        }
        p->next = l1 ? l1 : l2;
        return ret->next;
    }
};