leetcode

主要参考：

• 先后指针
• leetcode部分题目
• • 链表
  • • 206. 反转链表
    • 83. 删除排序链表中的重复元素
    • 19. 删除链表的倒数第 N 个结点
    • 160. 相交链表
  • 数组
  • 字符串

leetcode中链表的声明

206. 反转链表
思路：
pre cur 一前一后同步往后走

class Solution {
public:
    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->val < l1->val
        	l2->next = mergeTwoLists(l1, l2->next);
        	return l2;
        }
    }
};

思路：
先后指针 两个同时往后走

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL || head->next==NULL){
            return head;
        }
        ListNode *pre=head;
        ListNode *cur=head->next;
        while(cur!=NULL){
            if(cur->val==pre->val){
                pre->next=cur->next;
                cur=cur->next;
            }
            else{
                pre=pre->next;
                cur=cur->next;    
            }   
        }
        return head;
    }
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //两个指针一起走、n为多少两个指针离多远
        //这样只需要遍历一次就可以得到最终的结果
        ListNode* dummy = new ListNode(0, head);//哑节点
        ListNode* pb = head;
        ListNode* pa = dummy;
        for (int i = 0; i < n; ++i) {
            pb = pb->next;
        }
        while (pb) {
            pa = pa->next;
            pb = pb->next;
        }
        pa->next = pa->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

题目：找出两个单链表相交的起始节点；如果不存在相交节点 则返回NULL

解法一：直接遍历
注意：
不是找第一个相同的，而是找从该位置开始 后面都相同

class Solution {
public:
    ListNode *getIntersectionNode1(ListNode *headA, ListNode *headB) {                                
        ListNode *pA=headA;
        ListNode *pB=headB;
        while(pA!=NULL){
            while(pB!=NULL){
                if(pA == pB){
                    return pA;
                }
                pB=pB->next;
            }
            pB=headB;
            pA=pA->next;
        }
        return pA;
    }
};

解法二：双指针

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
          
        if(headA == nullptr || headB == nullptr){
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while(pA != pB){
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }


};