链表算法练习day.2_算法

24.两两交换链表中的节点

题目描述：

思路：

实现：

代码实现：

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     struct listnode *next;
 * };
 */
struct listnode* swappairs(struct listnode* head) {
    //创建一个虚拟头结点
    struct listnode *nhead = (struct listnode*)malloc(sizeof(struct listnode));
    nhead->next = head;

    //创造循环变量指针
    struct listnode *cur = nhead;

    //循环交换结点
    while(cur->next && cur->next->next)
    {
        //定义两个临时变量，记录交换之后可能会丢失的结点
        //记录要交换的第一个结点的位置
        struct listnode *loca1 = cur->next;
        //记录要交换的第二个结点的后一个结点
        struct listnode *loca2 = cur->next->next->next;
        //进行结点交换
        cur->next = cur->next->next; // 虚拟的头结点指向第二个结点（第一次交换）
        cur->next->next = loca1;  //第二个结点指向第一个结点
        loca1->next  = loca2; // 第一个结点指向第二个结点的后继结点

        cur = cur->next->next; //一次会操作两个结点，因此需要移动两位
    }

    return nhead->next;
}

易错点：

19.删除链表的倒数第n个结点

链接：. - 力扣（leetcode）

题目描述：

思路：

实现：

问题：为什么要让快指针走先走n+1步而不是n步呢

答：因为快指针如果先走n步，后序快慢指针一起移动，那么当快指针恰好指向为空时，那么慢指针的位置恰好就是我们要删除的倒数第n个结点，这样我们就难以查找到该结点的前驱点，因此让快指针先走n步，后序一起走，当快指针停下时，慢指针刚好就为前驱点，便于我们去删除结点。

代码实现：

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     struct listnode *next;
 * };
 */
struct listnode* removenthfromend(struct listnode* head, int n) {
    //定义一个虚拟头结点，让其指向头结点
    struct listnode *nhead = (struct listnode*)malloc(sizeof(struct listnode));
    nhead->next = head;

    //定义快慢指针
    struct listnode *fast = nhead;
    struct listnode *slow = nhead;
    //快指针先走n+1步
    for(register int i = 0 ; i <= n ; i++)
        fast = fast->next;
    //快慢指针一起走，指定快指针为空
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    //删除倒数第n个结点
    struct listnode *del = slow->next;//记录要删除的结点，需要释放内存
    slow->next = slow->next->next;
    free(del);

    //删除虚拟头结点
    head = nhead->next;
    free(nhead);
    
    return head;
}

160.相交链表

链接：. - 力扣（leetcode）

题目描述：

思路：

实现：

代码实现：

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     struct listnode *next;
 * };
 */
struct listnode *getintersectionnode(struct listnode *heada, struct listnode *headb) {
    //定义指针来遍历链表，并计算出链表长度
    struct listnode *lg = null; //记录较长的链表
    struct listnode *shr = null;//记录较短的链表
    int lena = 0 ,lenb = 0;  //记录两个链表的长度
    lg = heada;
    while(lg) //计算heada的长度
    {
        lg = lg->next;
        lena++;
    }
    lg = headb;
    while(lg)//计算headb的长度
    {
        lg = lg->next;
        lenb++;
    }
    //求两个链表的长度差
    int add = 0;
    if(lena > lenb)
    {
        lg = heada;
        shr = headb;
        add = lena - lenb;
    }
    else
    {
        lg = headb;
        shr = heada;
        add = lenb-lena;
    }

    //进行尾部对其
    while(add--)
        lg = lg->next;
    //查找是否有相同的元素
    while(lg)
    {   //查找到交叉的结点
        if(lg == shr)
            return lg;
        //没有查找到
        lg = lg->next;
        shr = shr->next;
    }
    //只要程序没有退出，则证明没有交叉的结点，返回为空
    return null;
}

142.环形链表

链接：. - 力扣（leetcode）

题目描述：

思路：

实现：

代码实现：

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     struct listnode *next;
 * };
 */
struct listnode *detectcycle(struct listnode *head) {
    //定义快慢指针，都指向链表头
    struct listnode *fast = head;
    struct listnode *slow = head;
    //让快指针一次移动两格，慢指针一次移动一格
    //快指针一次移动两个结点
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        //如果快慢指针相遇,说明找到了环
        if(fast == slow)
        {
            //定义一个指针记录相遇的位置
            struct listnode *index1 = fast;
            //再定义一个指针指向链表头，让他们同时移动
            struct listnode *index2 = head;
            //当这两个指针相遇，代表找到了环的入口
            while(index1 != index2)
            {
                index1 = index1->next;
                index2 = index2->next;
            }
            //如果退出循环，则返回环的入口位置
            return index1;
        }
    }
    //证明没有找到环
    return null;
}