数据结构与算法链表

　　链表
　　关于单链表，比较特殊，在面试中，要时刻注意时间复杂度和额外空间复杂度的问题
　　所以在笔试中，额外空间的应用无所谓，能做到即可，可以使用数组作为额外空间来使用
　　而在面试中要注意把额外空间复杂度降到最小，所以用克隆的方式来代替额外空间
　　这样子可以用不多的几个变量来确定关系，而位置的关系是通过克隆的位置关系来去确定的，这样的好处是让复杂度变低的同时还达到很好的效果桶排序
　　基数排序：分别按照个十百为先分别排序，然后再往上排序，对于每一位都是已经排好序，虽然不用进行比较，但是花费的空间和时间 比较多基本稳定
　　在排完序之后还保持着排序前的基本序列，在班级中按照成绩排，相同的排序按照学号前后综合排序
　　在小样本的时候采用一种排序方式，大样本的时候采用另一种，让整体复杂度减小哈希表
　　无序的，但有序表的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直接指向下一个奇数，偶数则成为奇数的nextclass 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;     } };