链表的题型和解题思路-ag真人游戏

1.链表中环的入口节点

首先判断头指针是不是空的
然后需要判断这个链表中包不包含环：两个指针，一个一步一个两部，如果相遇，说明存在
然后判断环节点的个数：从相遇的位置开始，往前走并计数，直到和自己再次相遇，得到个数
然后找出入口节点：从头开始，俩指针一个先走n步，另一个再走，两个相遇的位置就是入口节点位置

2.翻转链表

需要判断链表是不是空的或者链表是不是只有一个节点，如果是的话，直接就输出原来的链表了；

如果不是的话，翻转利用循环来做，因为需要将当前节点指向前一个节点，所以后一个节点需要先保存位置，也就是需要三个指针，一个ppre，一个pcur，一个pnext：先保存后一个节点，然后把当前节点指向前一个节点，然后把当前节点变成上一个节点，下一个节点变成当前节点；注意翻转之后头结点是原来的最后一个节点。

3.从尾到头打印链表

思路（1）：可以先翻转链表，再逐个输出

思路（2）：这种具有“后进先出”特性的，用栈比较容易，创建一个栈存放链表的节点，存放完之后从栈顶依次取出即可

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

举例子：
1 2 5 9 6 3 0
   7 8 9 6 3 0

首先需要知道的是，两个链表从公共节点开始，之后的节点肯定都是一模一样的；

可以先遍历得到两个链表各自的长度，然后让长的那个先走比另一个长出的步数，再同时走，判断哪里相等哪里就是第一个公共节点了

5.链表中倒数第k个节点

单向链表肯定是不能从后往前数的，这个跟上面有的类似，既然知道是倒数第k个，那就两个指针，让一个先走k-1步，然后两个同时走，判断先走的那个到尾结点了，那后走的那个就是倒数第k个节点。

6.删除链表中重复的节点

例如：1 2 3 3 4 4 5结果是1 2 5

首先需要判断头指针（第一个节点）和第二个节点是不是空的，如果是，返回头指针就行了；

正常情况的时候，因为有可能存在删除第一个节点的情况，所以需要先重新创建一个头指针listnode* newhead = new listnode(-1)，然后把这个头指针赋初值指向原本的头指针newhead->next = phead；

然后需要三个指针来解决这个问题，分别是ppre pcur pnext三个，ppre 赋初值newhead,pcur赋初值phead, 利用当前节点的循环来进行：得判断当前节点和当前节点的下一个节点不为空才进入循环来查找和删除，因为里头要对节点进行删除，所以要先保存下一个节点，然后如果当前节点等于下一个节点的值，因为还要继续判断下一位，来一个循环，只要下一个节点和当前节点的值相等，就把pnext往后移一个，直到找到不相等的就退出这个查找的循环了；然后执行删除，也就是把上一个节点ppre的下一个节点变成pnext，当前操作循环的节点变成pnext,然后再去循环判断；

那如果当前节点和下一个节点的值不相等呢：指针往后挪，循环再判断，也就是ppre = pcur；pcur = pcur->next。

最后返回新的头结点newhead的下一个节点即可。

7.复制复杂的链表

分成三个步骤：
（1）复制原始链表的任意节点n并创建新节点n'，把节点n'链接到节点n的后面
（2）设置复制出来的节点的random，假设原始链表上的n的random指向节点s，那么其对应复制出来的n'是n的next指向的节点，同样s'也是s的next指向的节点
（3）把整个链表根据奇数偶数分出两个链表来，偶数的就是拷贝的链表

/*
struct randomlistnode {
    int label;
    struct randomlistnode *next, *random;
    randomlistnode(int x) :
            label(x), next(null), random(null) {
    }
};
*/
class solution {
public:
    randomlistnode* clone(randomlistnode* phead)
    {
        if(phead == nullptr)
            return nullptr;
        //分成三个步骤：
        //1.复制原始链表的任意节点n并创建新节点n'，把节点n'链接到节点n的后面
        //2.设置复制出来的节点的random，假设原始链表上的n的random指向节点s，那么其对应复制出来的n'是n的next指向
        //的节点，同样s'也是s的next指向的节点
        //3.把整个链表根据奇数偶数分出两个链表来，偶数的就是拷贝的链表
        clonednode(phead);
        setrandom(phead);
        return reconnectnodes(phead);
    }
    void clonednode(randomlistnode* phead)
    {
        randomlistnode* pnode = phead;
        while(pnode != nullptr)
        {
            randomlistnode* newnode = new randomlistnode(0);//创建新节点
            newnode->label = pnode->label;
            newnode->next = pnode->next;
            newnode->random = nullptr;
            pnode->next = newnode;
            pnode = newnode->next;
        }
    }
    void setrandom(randomlistnode* phead)
    {
        randomlistnode* pnode = phead;
        while(pnode != nullptr)
        {
            randomlistnode* pcloned = pnode->next;
            if(pnode->random != nullptr)//这一步判断别忘了，如果为空，会造成程序瘫痪
                pcloned->random = pnode->random->next;
            else
                pcloned->random = nullptr;
            pnode = pcloned->next;//pnode往后移一位
        }
    }
    randomlistnode* reconnectnodes(randomlistnode* head)
    {
        randomlistnode* pnode = head;//循环操作
        randomlistnode* pclonedhead = nullptr;
        randomlistnode* pclonednode = nullptr;//创建一个新节点，作为拷贝链表的头结点
        if(pnode != nullptr)
        {
            pclonedhead = pclonednode = pnode->next;
            pnode->next = pclonednode->next;
            pnode = pnode->next;
        }
        while(pnode != nullptr)
        {
            pclonednode->next = pnode->next;
            pclonednode = pclonednode->next;
            pnode->next = pclonednode->next;
            pnode = pnode->next;
        }
        
        return pclonedhead;
    }
};

 8.翻转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

这个题说是翻转链表，其实就是改变了链表的头尾节点而已。

（1）先判断特殊情况，比如链表是否为空，是否只有一个元素，翻转的k是否为0等，否则直接返回

（2）然后处理一般情况，得先遍历一次得到链表的总长度size，然后将链表首尾相接，成为一个循环链表

（3）根据size和k的关系，计算出循环链表循环的次数loot= size - (k%size);

（4）然后进行指针循环，之前的头尾节点指针开始移动，次数为loop，直到移动结束，原先的尾结点指针指向的为新链表的尾部，原先的头结点指针指向的为新链表的头部。

9.扁平化多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

 这题太经典了！

/*
// definition for a node.
class node {
public:
    int val;
    node* prev;
    node* next;
    node* child;
};
*/
class solution {
public:
    vector v;
    //这题就是二叉树的前序遍历
    //可以先前序遍历，将所有节点放入容器中，然后再顺序进行前后连接
    void dfs(node* head)
    {
        if(head == nullptr)
            return;
        v.push_back(head);
        dfs(head->child);
        dfs(head->next);
    }
    node* flatten(node* head) {
        dfs(head);//这样就将所有的节点放入了容器中，按照前序的方式
        int n = v.size();//得到容器中的节点数
        for(int i=0;i)
        {
            if(i1)
                v[i]->next = v[i 1];
            if(i>0)
                v[i]->prev = v[i-1];
            v[i]->child = nullptr;
        }
        return head;
    }
};

10.判断是不是回文链表

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     listnode *next;
 *     listnode(int x) : val(x), next(null) {}
 * };
 */
class solution {
public:
    bool ispalindrome(listnode* head) {
        //先判断特殊情况
        if(head == nullptr || head->next == nullptr)
            return true;
        //然后一般情况的判断方式是：先找到链表的中点，然后翻转后半部分，然后进行比较
        listnode* fast = head;
        listnode* slow = head;
        while(fast != nullptr)
        {
            slow = slow->next;
            fast = fast->next? fast->next->next : fast->next;
        }
        //最后的slow为原来链表的中间节点，也是待会儿需要翻转链表的头结点
        //fast则指向了nullptr
        
        //然后需要进行翻转
        listnode* ppre = nullptr;
        while(slow != nullptr)
        {
            listnode* temp = slow->next;//存储下一个节点
            slow->next = ppre;
            ppre = slow;
            slow = temp;
        }
        //然后进行判断
        while(ppre != nullptr && head != nullptr)
        {
            if(ppre->val != head->val)
                return false;
            ppre = ppre->next;
            head = head->next;
        }
        return true;
    }
};

tips：遇到链表为题时候的思考方式

（1）是否能用双指针解决

（2）知否可以将一个指针先走几步，再两个同时走解决

（3）是否需要知道链表节点的个数

（4）是否需要将链表变成循环链表处理

（5）考虑是否需要容器，容器可以放节点，容器的好处也是能知道链表的长度

（6）找链表的中点、翻转链表都是最基本的操作，在拔高的题目里头有可能会用到