哨兵节点哨兵节点是为简化链表边界条件的处理而引入的附加链表节点。哨兵节点通常位于链表的头部，它的值没有意义。在带有哨兵节点的链表中，从第二个节点开始只保存有意义的信息。使用哨兵节点简化链表插入操作使用哨兵节点简化链表删除操作使用哨兵节点简化创建或删除链表头节点的代码。双指针删除倒数第k个节点题目：给定一个链表，如何删除链表倒数第k个节点？假设链表的节点总数为n，则1≤k≤n。要求链表只能遍历一次。/***@param{ListNode}head*@param{number}n*@return{ListNode}*/varremoveNthFromEnd=function(head,n){constdummy=newListNode(0,head);设前=头，后=假人；for(leti=0;i=10){val=val-10node=newListNode(val)sub=1}else{node=newListNode(val)sub=0}head.next=nodehead=head.nexthead1&&(head1=head1.next)head2&&(head2=head2.next)}if(sub==1){head.next=newListNode(1)head=head.next}returnreverseList(dummy.next)};重排链表问题：给定一个链表，链表中节点的顺序为L0→L1→L2→...→Ln-1→Ln，如何重排链表使节点的顺序变为L0→Ln→L1→Ln-1→L2→Ln-2→…？拆分链表和反转半链表后/***单链表的定义。*functionListNode(val,next){*this.val=(val===undefined?0:val)*this.next=(next===undefined?null:next)*}*/varreverseList=function(head){letprev=nullletcur=headwhile(cur!==null){constnext=cur.nextcur.next=prevprev=curcur=next}returnprev}/***@param{ListNode}head*@return{void}不要返回任何东西，而是就地修改head。*/varreorderList=function(head){letdummy=newListNode(0,head);让快=虚拟，慢=虚拟；while(fast!=null&&fast.next!=null){slow=slow.nextfast=fast.next.next}consttemp=slow.next;慢.next=null;link(head,reverseList(temp),dummy);}varlink=function(node1,node2,head){让prev=head;while(node1!==null&&node2!==null){consttemp=node1.next;prev.next=node1;node1.next=node2prev=node2node1=tempnode2=node2.next}if(node1!==null){prev.next=node1}}回文链表问题：如何判断一个链表是否为回文链表？求解的时间复杂度为O(n)，必须使用不超过O(1)个辅助空间。如果链表是回文链表，则链表的节点顺序从前到后和从后到前相同。例如图4.13中链表的节点顺序从前到后和从后到前都是1,2,3,3,2,1，所以这是一个回文链表。/***单链表的定义。*functionListNode(val,next){*this.val=(val===undefined?0:val)*this.next=(next===undefined?null:next)*}*/varreverseList=function(head){letprev=nullletcur=headwhile(cur!==null){constnext=cur.nextcur.next=prevprev=curcur=next}returnprev}/***@param{ListNode}head*@return{boolean}*/varisPalindrome=function(head){if(head==null||head.next==null){返回真；}让慢=头；letfast=head.next;while(fast.next!==null&&fast.next.next!==null){slow=slow.nextfast=fast.next.next}letsecondHalf=slow.next;if(fast.next!=null){secondHalf=slow.next.next}slow.next=null;returnequals(secondHalf,reverseList(head))}varequals=function(head1,head2){while(head1!=null&&head2!==null){if(head1.val!==head2.val)返回falsehead1=head1.nexthead2=head2.next}returnhead1==null&&head2==null;}双向链表和循环链表扁平化多层双向链表在多层双向链表中，节点有两个指针分别指向前后两个节点，都有指向其子链表的指针，子链表也是双向链表，其节点也有指向子链表的指针。请把这样一个多级双向链表展平成一个普通的双向链表，即所有的Node都没有子链表。深度遍历varflatten=function(head){constdfs=(node)=>{letcur=node;//记录链表的最后一个节点letlast=null;while(cur){letnext=cur.next;//如果有子节点，则先处理子节点if(cur.child){constchildLast=dfs(cur.child);下一个=当前下一个；//将节点连接到子节点cur.next=cur.child;当前.child.prev=当前；//如果next不为空，将last连接到nextif(next!=null){childLast.next=next;next.prev=childLast;}//将child设置为nullcur.child=null;最后一个=孩子最后一个；}else{last=cur;}cur=下一个；最后返回；}dfs（头）；返回头；}；增量排序，请设计一种算法，在循环链表中插入节点，并保证插入节点后的循环链表仍然是有序的。
