单链表算法题(数据结构)

标签：单链 ListNode struct fast next 链表算法数据结构指针

1. 反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

题目：

看到这个题目的时候我们怎么去想呢？如果我们反应快的话，应该可以想到我们可以从1遍历到5然后依次头插，但是其实我们还有更好的办法，就是利用三个指针，如何使用呢？

反转链表OJ
假如结构体已经给出
typedef struct ListNode SL;
SL* reverseList(SL* head)
{
    //处理空链表
    if (head == NULL)
    {
        return head;
    }
    else
    {
        //创建三个指针
        SL* n1, n2, n3;
        n1 = NULL, n2 = head, n3 = n2->next;
        while (n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
            {
                n3 = n3->next;
            }
        }
        return n1;

    }
}

2. 链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/description/ 题目：这个题目就是在一个链表中我们要返回中间结点，如果中间结点有两个的话就返回第二个结点。

对于这个题目我们可能会想到一个简单的思路，就是遍历两边数组然后找到中间的一个结点，但是呢，今天讲一个更方便的算法叫做快慢指针，也就如上图所示，一个慢指针和一个快指针，快指针走两步慢指针走一步，最终当快指针走到终的时候慢指针刚好就在中间，让我们来实现一下：

//找链表的中间结点
//Definition for singly-linked list.
struct ListNode
{
    int val;
    struct ListNode *next;
};
 
typedef struct ListNode SL;
struct ListNode* middleNode(struct ListNode* head)
{
	SL* slow = head;
	SL* fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}

再上一个题目中我们有一个点需要注意就是我们在写while循环的条件时候注意不能将fast&&fast->next的位置搞反，原因就是不能解引用空指针，所以顺序一定注意一下。

3. 合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/

题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。这个题目的思路也很好想出来，我们可以遍历两个升序链表，然后创建一个新的链表，将遍历的结点按升序放入新的链表中，要注意链表为空的情况。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode SL;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    //创建新的链表
    SL* newhead=NULL;
    SL* newtail=NULL;
    //创建两个指针分别指向两个链表
    SL* l1=list1;
    SL* l2=list2;
    //判断两个链表是否为空
    if(list1==NULL)
    {
        return l2;
    }
    if(list2==NULL)
    {
        return l1;
    }
    while(l1&&l2)
    {
        if(l1->val<=l2->val)
        {
            //l1尾插到新链表中
            if(newhead==NULL)
            {
                newhead=newtail=l1;
            }
            else
            {
                newtail->next=l1;
                newtail=newtail->next;
            }
            l1=l1->next;
        }
        else
        {
            //l2尾插到新链表中
            if(newhead==NULL)
            {
                newhead=newtail=l2;
            }
            else
            {
                newtail->next=l2;
                newtail=newtail->next;
            }
            l2=l2->next;

        }
    }
    //跳出循环有两种情况，要么l1为空，要么l2为空
    if(l1)
    {
        newtail->next=l1;
    }
    if(l2)
    {
        newtail->next=l2;
    }
    return newhead;
}

4. 链表的回文结构

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

什么是回文结构？比如1221，它看起来像是对称的可以从中间重叠的感觉，叫做回文数字。像上图1->2->2->1，就是链表的回文结构。我们就是思考如何去判读一个链表是否是回文结构。我们可能会想到说这个题目需要去遍历比较是否相等，但是有一个问题就是在单链表中是不能向后遍历的，又因为这个题目是的链表长度是有限的，所以我们不妨把链表放入数组中来比较，那么如何操作呢？

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) 
    {
        // write code here
        //创建一个数组
        int arr[900] = {0};
        ListNode* pcur = A;
        int i = 0;
        //遍历链表，将链表中的每个结点的数值放入数组中
        while(pcur)
        {
            arr[i++] = pcur->val;
            pcur=pcur->next;
        }
        //找中间结点，判断是否是回文数字
        int left=0;
        int right=i-1;
        while(left<right)
        {
            if(arr[left]!=arr[right])
            {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

对于这个题目来说，它是有限制的，所以我们可以放在数组中去双向遍历，但是一旦链表没有限制，我们就不能这样来写，我们可以有另一种方法，我们的前两道题目是反转链表和找中间结点，看下面的图，如果是回文链表的话我们可以先找到中间结点，然后将其反转成为一个新的链表，再创建两个指针遍历链表，判断链表结点是否相等，最终以一个指针为NULL而结束。

5. 相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //创建两个指针遍历链表
    ListNode* l1=headA;
    ListNode* l2=headB;
    //先计算两个链表的长度
    int sizeA=0;
    int sizeB=0;
    while(l1)
    {
        sizeA++;
        l1=l1->next;
    }
    while(l2)
    {
        sizeB++;
        l2=l2->next;
    }//得出了两个链表的长度
    //计算两数之差
    int gap=abs(sizeA-sizeB);
    //让长链表先走gap步
   
    ListNode* longlist=headA;
    ListNode* shortlist=headB;
    if(sizeA<sizeB)
    {
        longlist=headB;
        shortlist=headA;
    }
    while(gap--)
    {
        longlist=longlist->next;
    }
    //此时在同一个起点处，进行两个链表结点的比较
    while(longlist&&shortlist)
    {
        if(longlist==shortlist)
        {
            return longlist;
        }
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    //链表不相等
    return NULL;
}

6. 环形链表

https://leetcode.cn/problems/linked-list-cycle/description/

题目：给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。否则，返回 false 。

标签：单链,ListNode,struct,fast,next,链表,算法,数据结构,指针
From： https://blog.csdn.net/OKkankan/article/details/143608430