算法复习：链表

链表定义

struct ListNode { 
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

链表的遍历：ListNode p=head; while(p!=null) p=p.next; 

找到链表的尾结点：p=head; while(p.next!=null)p=p.next;

链表节点的个数：

          p=head; cnt=0; //cnt与p不同步对应

          while(p!=null)：cnt++; p=p.next

          cnt与p不同步对应的原因：

          while停止后,p为null,cnt为对应到最后一个节点上面

         规律：开始的时候同步和结束时候的同步规律是一致的。

链表删除

 注意：1.删除节点需要dummyNode  2.最后返回的是dummyNode.next而不是head.

       因为head可能被删掉

ListNode* deleteNode(ListNode* head, ListNode* p) {
        // 创建一个虚拟头节点，便于处理链表头部的删除操作
        ListNode dummyNode(0);
        dummyNode.next = head;
        // 将虚拟头节点的下一个节点指向原链表头节点
        ListNode* prev = &dummyNode;
        // 遍历链表，找到待删除节点的前驱节点
        while (prev->next&& prev->next != p) {
            prev = prev->next;
        }
        // 如果待删除节点存在，则进行删除操作
        if (prev->next) {
            prev->next = prev->next->next;
        } 
        else {
            std::cout << "Target node not found in the list." << std::endl;
        }
        // 返回处理后的新链表头节点（即原链表头节点）
        return dummyNode.next;
}

链表插入

  (1)头插法: dummyNode,p:

p.next=dummyNode.next;
dummyNode.next=p;

  (2)尾插法

tail,p:
   tail.next=p; tail=p;

   在尾插法的过程中,tail.next不需要清空:

   每次插入时tail.next都会重定向到待插入的节点

   最后tail.next=null

找到链表的第index个节点

int i=1;
p=head;
//计数变量和p索引始终同步对应:while停止后,i对应p.
while(i<index&&p!=null)
     p=p.next;
     i++;

链表翻转： dummyNode + 头插法

   ListNode dummyNode=new ListNode();
   dummyNode.next=null;
   ListNode p=head;
   if(head==null)return null;
   ListNode q=p.next;
   while(p!=null)
       q=p.next;
       p.next=dummyNode.next;
       dummyNode.next=p;
       p=q;
   return dummyNode.next;

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

 (1)求两个链表长度n1,n2  

 (2)长的链表走|n1-n2|步,使两个链表长度相同

 (3)两个链表一起走,相等返回，走到头返回null

倒数第k个节点

(1) 求节点个数n

(2)求第n-k+1个节点

删除重复节点

 (1)增加虚拟头结点

   (2)链表节点的删除

     p.next=p.next.next

删除链表倒数第n个节点

   (1)添加虚拟头结点

   (2)求链表长度l

   (3)找第l-n的节点并删除

判断环

         如果有环:slow和fast走一定会相遇

         如果没有环:在有限次遍历链表后,一定为空

if head==null:return false//特判
slow=head;
fast=head.next;   
while(slow!=fast&&slow!=null&&slow.next!=null&&fast!=null&&fast.next!=null)
       slow=slow.next;
       fast=fast.next.next;
       if(slow==fast)return true;
       return false 

判断环的入口

(1)fast和slow置头结点,速度为2,1

(2)相遇后fast置头结点，速度为1

(3)fast和slow相遇的节点是入口

fast=pHead;
slow=pHead;
while(fast!=null&&fast.next!=null){
     fast=fast.next.next;slow=slow.next;
     if(fast==slow){
          fast=pHead;
          while(fast!=slow){
              fast=fast.next;
              slow=slow.next;}
          return fast;
return nullptr//如果遍历到空节点,说明没有环,返回null

合并两个排序的链表

p=head1,q=head2;
tail = dummyNode;
while(p!=null&&q!=null){
     if(p.val<q.val)tail.next=p;tail=p;p=p.next;
     else  tail.next=q;tail=q;q=q.next;
}

tail直接指向非空的一个链表,如果两个链表都是空,那么就指向空
tail.next=(p==null)?q:p;
return dummyNode.next;

回文链表

存储链表的值

指定区间反转链表

？

思路：切断后反转局部链表后重接回去。node1,node2,..,p,start,...end,q...noden

需要找到p,q,start,end

 (1)把区间的链表单独拎出来:

 p.next=null; end.next=null;

 (2)反转区间reverse

 (3)重写接回去

  reverse(start);

增加虚拟头结点:

  如果说从第一个开始就翻转,那么就得分情况讨论,所以要添加一个虚拟头结点。

奇偶链表

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。 O(1) 的额外空间复杂度和 O(n) 的时间复杂度

两个虚拟头结点，使用尾插法，然后合并到一起。

ListNode *odd = new ListNode(0);
ListNode *even = new ListNode(0);

 ListNode *tail1=odd;
 ListNode *tail2=even;
 ListNode *p = head;
 int idx=1;
  while(p!=nullptr){
       if(idx%2!=0){
                tail1->next=p;
                tail1=p;
                p=p->next;
                idx++;
        }else{
                tail2->next=p;
                tail2=p;
                p=p->next;
                idx++;
            }
        }
//最后需要把tail2->next置空
        tail2->next=nullptr;
        tail1->next=even->next;
        return odd->next;
 }

尾插法最后置空，否则会出现野指针错误。