链表

关于单链表，比较特殊，在面试中，要时刻注意时间复杂度和额外空间复杂度的问题

所以在笔试中，额外空间的应用无所谓，能做到即可，可以使用数组作为额外空间来使用

而在面试中要注意把额外空间复杂度降到最小，所以用克隆的方式来代替额外空间

这样子可以用不多的几个变量来确定关系，而位置的关系是通过克隆的位置关系来去确定的，这样的好处是让复杂度变低的同时还达到很好的效果

桶排序

基数排序：分别按照个十百为先分别排序，然后再往上排序，对于每一位都是已经排好序，虽然不用进行比较，但是花费的空间和时间 比较多

基本稳定

在排完序之后还保持着排序前的基本序列，在班级中按照成绩排，相同的排序按照学号前后

综合排序

在小样本的时候采用一种排序方式，大样本的时候采用另一种，让整体复杂度减小

哈希表

无序的，但有序表的key是有序的

增删改查的复杂度都是常数，但是这个常数可能比较大

unordermap,unordertree

快慢指针求回文

也可以申请栈，将每个数遍历后都放进栈里面去，然后依次弹出，比较

可以采用快慢指针的方式，但是将头结点的下一位做慢指针，可以解决奇数和偶数问题

随机哈希表的设置

设置一个哈希表，将每个数的next和rand都放进哈希表里，第一次遍历老链表就是放进哈希表，第二次是根据哈希表里的next和rand，设置新链表的next和rand

直接插入克隆结点在当前结点后面，这样的话就不用在哈希表里设置next了，然后在遍历的时候设置一下边界，一对对遍历，存入rand即可，克隆节点的rand就是原本节点rand的克隆节点

有环链表

可以申请哈希表额外空间，记录每个遍历后的结点，第一次重复访问到的节点就就是环的开头

快慢指针：一开始都在head，慢指针一次走一步，快指针一次走两步，会在环里相遇，相遇后，快指针回到head，快慢指针同时走，都走一步，最终会在环的开始节点相遇

无环链表

判断两条链表是否在同一地址，即最后节点是否相同，因为当两条单链表有相交时，相交部分一定是相同的，next指针是不会断的。

判断最后节点相同时即可判断出他们相交

让长链表先走x 步，x为二者差值，然后二者同时走，一定会在相交节点相遇

cur1 = n>0 ? head1 : head2//谁长，谁的头是head1
cur2 = cur1 == head1 ? head2 : head1 //谁短，谁的头是cur2

重定位长短

如果是相同环，则把终止节点设置为俩链表入环节点，其余按照无环链表操作，如果不同环，从loop 1开始，如果遇得到loop2，则是不同入环节点，返回谁都可以，但如果没有，则不相交

合并k 个已排序链表

思路：多个指针，有限几个变量，采用merge方法，拆分出左右两组链表，然后进行合并，大化小

• step 1：从链表数组的首和尾开始，每次划分从中间开始划分，划分成两半，得到左边n/2n/2n/2个链表和右边n/2n/2n/2个链表。
• step 2：继续不断递归划分，直到每部分链表数为1.
• step 3：将划分好的相邻两部分链表，按照两个有序链表合并的方式合并，合并好的两部分继续往上合并，直到最终合并成一个链表。

class Solution {
public:
    ListNode *Merge2(ListNode *phead1, ListNode *phead2){
        if(phead1 == NULL) return phead2;
        if(phead2 == NULL) return phead1;
        ListNode *head = new ListNode(0);
        ListNode *cur = head;
        while(phead1 && phead2){
            if(phead1->val > phead2->val){
                cur->next = phead2;
                phead2 = phead2->next;
            }
            else{
                cur->next = phead1;
                phead1 = phead1->next;
            }
            cur = cur->next;
        } 
        if(phead1) cur->next = phead1;
        else cur->next = phead2;
        return head->next;
    }
    ListNode *pideMerge(vector &lists, int left, int right){
        if(left > right) return NULL;
        else if (left == right) return lists[left];
        int mid = (left + right) / 2;
        return Merge2(pideMerge(lists, left, mid), pideMerge(lists, mid+1, right));
    }

    ListNode *mergeKLists(vector &lists) {
        return pideMerge(lists, 0, lists.size() - 1);
    }
};

链表中环的入口节点

• 可以采用哈希表，放进去的节点遇到重复的第一个就是入环节点
• 快慢指针：快指针走两步，慢指针走一步，当快慢指针相遇时，快指针返回起点，快慢指针一起走，都是走一步，再次相遇的节点就是入环节点

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead == NULL ) return NULL;
        ListNode *slow = pHead;
        ListNode *fast = pHead;
        
        while(fast != NULL && fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
                break;
        }
        if(fast == NULL || fast->next == NULL)
            return NULL;
        fast = pHead;
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

链表中倒数最后k个结点

• 两次遍历的方法，先统计总长，然后n-k次遍历找到
• 可以快慢指针，快指针先走k步，然后和慢指针一起走

class Solution {
public:
   ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        while(pHead == NULL) return NULL;
        ListNode *fast = pHead;
        ListNode *slow = pHead;
        for(int i=0; inext;
            
        }
        while(fast != NULL ){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;

    }
};

删除链表的倒数第n个结点

class Solution {
  public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            //添加表
            ListNode* res = new ListNode(-1);
            res->next = head;
            //当前节点
            ListNode* cur = head;
            //前序节点
            ListNode* pre = res;
            ListNode* fast = head;
            //快指针先行n步
            while (n--)
                fast = fast->next;
            while (fast != NULL) {
                fast = fast->next;
                pre = cur;
                cur = cur->next;
            }
            //删除该位置的节点
            pre->next = cur->next;
            //返回去掉头
            return res->next;
        }
};

两个链表的第一个公共结点

• 循环遍历两个链表，迟早会相遇

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1, l2 = pHead2;
        while(l1 != l2){
            l1 = (l1==null)?pHead2:l1.next;
            l2 = (l2==null)?pHead1:l2.next;
        }
        return l1;
    }

• 额外空间的，所有都存进去，看是否有相同的
• 双指针，先走差值步，然后同时遍历，第一个相同的就是公共结点

链表相加

• 采用反转链表的方式

class Solution {
public:
    ListNode *reverselist(ListNode *phead){
        if(phead == NULL) return phead;
        ListNode *cur = phead;
        ListNode *pre = NULL;
        while(cur != NULL){
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        if(head1 == NULL) return head2;
        if(head2 == NULL) return head1;
        head1 = reverselist(head1);
        head2 = reverselist(head2);
        ListNode *res = new ListNode(-1);
        ListNode *head = res;
        int carry = 0;
        while(head1 != NULL || head2 != NULL || carry !=0){
            int val1 = head1 == NULL ? 0:head1->val;
            int val2 = head2 == NULL ? 0 : head2->val;
            int temp = val1 + val2 + carry;
            carry = temp/10;
            temp %= 10;
            head->next = new ListNode(temp);
            head = head->next;
            if(head1 != NULL){
                head1 = head1->next;
            }
            if(head2 != NULL){
                head2 = head2->next;
            }
        }
        return reverselist(res->next);
    }
};

• 采用辅助空间的方式

public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1 == null)
            return head2;
        if(head2 == null){
            return head1;
        }
        // 使用两个辅助栈，利用栈先进后出，相当于反转了链表
        Stack stack1 = new Stack<>();
        Stack stack2 = new Stack<>();
        ListNode p1=head1;
        ListNode p2=head2;
        // 将两个链表的结点入栈
        while(p1!=null){
            stack1.push(p1);
            p1=p1.next;
        }
        while(p2!=null){
            stack2.push(p2);
            p2=p2.next;
        }
        // 进位
        int tmp = 0;
        // 创建新的链表头节点
        ListNode head = new ListNode(-1);
        ListNode nHead = head.next;
        while(!stack1.isEmpty()||!stack2.isEmpty()){
            // val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值）
            int val = tmp;
            // 栈1不为空的时候，弹出结点并累加值
            if (!stack1.isEmpty()) {
                val += stack1.pop().val;
            }
            // 栈2不为空的时候，弹出结点并累加值
            if (!stack2.isEmpty()) {
                val += stack2.pop().val;
            }
            // 求出进位
            tmp = val/10;
            // 进位后剩下的数值即为当前节点的数值
            ListNode node = new ListNode(val%10);
            // 将结点插在头部
            node.next = nHead;
            nHead = node;
        }
        if(tmp > 0){
            // 头插
            ListNode node = new ListNode(tmp);
            node.next = nHead;
            nHead = node;
        }
        return nHead;
    }
}

单链表的排序

• 数组形式：创建一个数组，将链表内容放入，然后排序完恢复链表形式

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        vector nums; 
        ListNode* p = head;
        //遍历链表，将节点值加入数组
        while(p != NULL){ 
            nums.push_back(p->val);
            p = p->next;
        }
        p = head;
        //对数组元素排序
        sort(nums.begin(), nums.end()); 
        //遍历数组
        for(int i = 0; i < nums.size(); i++){ 
            //将数组元素依次加入链表
            p->val = nums[i]; 
            p = p->next;
        }
        return head;
    }
};

• 递归形式：每次分成两部分，然后将分割后的部分进行局部排序，最终达到整体有序

class Solution {
public:
    ListNode *mergelist(ListNode *phead1, ListNode *phead2){
        if(phead1 == NULL) return phead2;
        if(phead2 == NULL ) return phead1;
        ListNode *head = new ListNode(0);
        ListNode *cur = head;
        while(phead1 && phead2){
            if(phead1->val >phead2->val){
                cur->next = phead2;
                phead2 = phead2->next;
            }else{
                cur->next = phead1;
                phead1 = phead1->next;
            }
            cur = cur->next;
        }
        if(phead1) cur->next = phead1;
        else cur->next = phead2;
        return head->next;
    }
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(head == NULL || head->next == NULL) return  head;
        ListNode *left = head;
        ListNode *mid = head->next;
        ListNode *right = head->next->next;
        while(right != NULL && right->next != NULL){
            left = left->next;
            mid = mid->next;
            right = right->next->next;
        }
        //左边指针指向左段的左右一个节点，从这里断开
        left->next = NULL;
         //分成两段排序，合并排好序的两段
        return mergelist(sortInList(head), sortInList(mid));
    }
};

判断链表是否为回文结构

• 存入数组的方式，然后将数组反转后对比
• 存入数组的方式，得到数组长度，双指针分别从两端开始

class Solution {
public:
    bool isPail(ListNode* head) {
        vector nums;
        //将链表元素取出一次放入数组
        while(head != NULL){ 
            nums.push_back(head->val);
            head = head->next;
        }
        //双指针指向首尾
        int left = 0; 
        int right = nums.size() - 1;
        //分别从首尾遍历，代表正序和逆序
        while(left <= right){ 
            //如果不一致就是不为回文
            if(nums[left] != nums[right]) 
                return false;
            left++;
            right--;
        }
        return true;
    }
};

• 快慢指针方式，记录到中间位置，然后反转后半部分，再对比（满足时间O(n)，空间O(1)）

class Solution {
public:
    ListNode *reverse(ListNode *head){
        ListNode *pre = NULL;
        while(head != NULL){
            ListNode *next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    bool isPail(ListNode* head) {
        // write code here
        ListNode *slow = head->next;
        ListNode *fast = head;
        while(fast->next != NULL && fast->next->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = head;
        slow = reverse(slow);
        while(slow != NULL){
            if(fast->val != slow->val) return false;
            slow = slow->next;
            fast = fast->next;
        }
        return true;
    }
};

链表的奇偶重排

• 双指针的方式，将偶数的节点跳过，奇数的next直接指向下一个奇数，偶数则成为奇数的next

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        if(head == NULL) return NULL;
        ListNode *even = head->next;
        ListNode *odd = head;
        ListNode *evenodd = even;
        while(even != NULL && even->next != NULL){
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenodd;
        return head;
    }
};

删除有序链表中重复的所有元素

• 从0开始，不从1开始，这样的话可以从重复节点的上一个开始判断，每一次遇到重复前都可以判断出后面两个是否有重复元素

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
       if(head == NULL) return NULL;
       ListNode *res = new ListNode(0);
       res->next = head;
       ListNode *cur = res;
       while(cur->next != NULL && cur->next->next != NULL) {
           if(cur->next->val == cur->next->next->val){
               int temp = cur->next->val;
               while(cur->next != NULL && cur->next->val == temp){
                   cur->next = cur->next->next;
               }
           }else cur = cur->next;
 
       }
       return res->next;
    }
};