一.内容介绍

1.链表翻转—头插入法+哑节点+双指针

https://blog.csdn.net/FX677588/article/details/72357389-链表翻转
对于非递归形式的链表翻转

  1. if(head==nullptr||head->next==nullptr)
  2.     return head;
  3. ListNode dummpy(0,head);
  4. ListNode *pptr=&dummpy,*qptr=head,*moveptr;
  6. while(qptr!=nullptr) {
  7.     moveptr=qptr->next;
  8.     if (moveptr==nullptr)
  9.         break;
  10.        qptr->next=moveptr->next;
  11.     moveptr->next=pptr->next;
  12.     pptr->next=moveptr;
  13. }
  14. qptr->next=nullptr;
  15. return dummpy.next;

对于用递归方法image.png

node* In_reverseList(node* H)
{
    if (H == NULL || H->next == NULL)       //链表为空直接返回，而H->next为空是递归基
        return H;
    node* newHead = In_reverseList(H->next); //一直循环到链尾（递归到链表尾部） 
    H->next->next = H;                       //翻转链表的指向
    H->next = NULL;                          //记得赋值NULL，防止链表错乱
    return newHead;                          //新链表头永远指向的是原链表的链尾
}

2.递归法

3.链表操作小技巧

  • 在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了，并且在返回的时候，只需要返回dummy.next即可。
  • 在问到链表的倒数第k个节点时，可以用双指针，先让前指针向前移动k位，然后两个指针同时移动。这种类似的思路，也即先移动，多少，然后同时移动
  • 链表的头插入法结合哑节点可以实现线性时间内对链表的反转。

    二.leetcode题

23.合并K个升序链表

题目链接

  1. 只想出了简单的顺序合并，还有归并合并、优先队列合并的方式需要继续研究一下

234.回文链表-(快慢指针找中点，翻转比较)

题目链接
方法一：
先遍历一遍链表，然后把相应的值都存下来，然后再遍历一遍链表，与存储的值反向比较即可。

方法二：不申请额外存储空间
快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。 当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。 若链表有奇数个节点，则中间的节点应该看作是前半部分。
找到前半部分链表的尾节点。
反转后半部分链表。
判断是否回文。

19.删除链表的倒数第N个结点-(双指针)

题目链接
在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。
采用双指针first和second，初始均指向dummpy node，然后second指针比first指针超前n个节点，然后两者同时遍历，在second指针到达尾部节点时(即second->next==nullptr)，first指针正好指向倒数第n个节点的前一个节点，然后再进行相关链接删除操作即可。

剑指Offer-18：删除链表的节点

题目： 在O(1)时间内删除链表节点 给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。链表节点与函数的定义如下： struct ListNode { int m_nValue; ListNode m_pNext; }; void DeleteNode(ListNode** pListHead, ListNode pToBeDeleted )

正常的思路可能是遍历链表去找到要删除节点A的前一个节点B，然后将B的next指向A的下一个节点C。不过这样的话，时间复杂度为O(n)。
这里可以把要删除的节点A的下一个节点C的内容覆盖到A上，然后删除C节点，如果A节点是尾节点，则需要特殊处理，遍历一下链表，如果链表只有一个节点，则需要把*pListHead置空。

92.反转链表||

题目链接

  1. 采用头插入法，对这个局部进行头插入，可以线性实现局部的链表反转； ```cpp ListNode reverseBetween(ListNode head, int left, int right) {
     if (head->next==nullptr||left==right)
     return head;
 ListNode dummpy(0,head);
 ListNode*g=&dummpy,*q=head,*nextptr;
 int count=1;
 while (count<right){
     if (count>=left){
         nextptr=q->next;
         q->next=nextptr->next;
         nextptr->next=g->next;
         g->next=nextptr;
         count++;
     }else {
         count++;
         g=g->next;
         q=q->next;
     }
 }
 return dummpy.next;

}

<a name="SCyuA"></a>
## 25.K个一组翻转链表
[题目链接](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)

1. 思路清晰，对变量的命名及其作用想明白就OK，
1. preptr指向已经排好序的部分的结尾，start指向未排好序的开始，end指向正在排序的段的末尾，也即刚开始未排序的段的开头
1. 先找出K个，再对这个K个翻转
```cpp
ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummpy(0,nullptr);
        ListNode*preptr=&dummpy,*end=&dummpy,*start=head,*iptr,*tmp;
        int i;
        while(1) {
            preptr=end;
            iptr=start;
            i=k;
            while(i>1&&iptr!=nullptr) {
                iptr=iptr->next;
                --i;
            }
            if (iptr==nullptr){
                preptr->next=start;
                break;
            }
            end=start;
            while(i<=k) {
                tmp=start;
                start=start->next;
                tmp->next=preptr->next;
                preptr->next=tmp;
                i++;
            }
        }
        return dummpy.next;
    }