LeetCode每日一刷 --- 手撕单链表习题（2）

1、链表的回文结构

• 链接直达：

链表的回文结构

• 题目： 思路：

找中间节点再逆置，此法非常巧妙，找中间节点和逆置这两块内容在上一份博文中已经详细讲解过，这里不多赘述，这样做的原因是执行上述操作后遍历原头节点和逆置后新头节点，判断值是否相等，若遍历后都相等则返回true，反之false。

• 代码如下：

class PalindromeList {
public:
//第一步：找到中间节点
    struct ListNode* middleNode(struct ListNode* head) {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
//第二部：逆置从中间节点开始往后的数据，并返回新的头节点
    struct ListNode* reverseList(struct ListNode* head) {
        if (head == NULL)
        {
            return NULL;
        }
        struct ListNode* n1 = head;
        struct ListNode* n2 = head->next;
        struct ListNode* n3 = NULL;
        while (n1)
        {
            n1->next = n3;
            n3 = n1;
            n1 = n2;
            if (n2)
            {
                n2 = n2->next;
            }
        }
        return n3;
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid = middleNode(A);
        struct ListNode* rHead = reverseList(mid);
        while (A && rHead)
        {
            if (A->val == rHead->val)
            {
                A = A->next;
                rHead = rHead->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};

2、相交链表

• 链接直达：

相交链表

• 题目： 思路：

法一：A链表的每个元素跟B链表依次比较，如果有相等，就是相交，第一个相等的就是交点。

此法的时间复杂度是O(M*N)，此法的优势就是在判断好是否相交后直接把相交的节点求出来了，注意：在比较的时候不能拿值去比较，要拿地址去比较。此法的缺陷就是效率相对较低，可以再进行改进。

法二：遍历原链表 + 快慢指针

先判断两个链表是否相交

依次遍历两个链表到尾，看两个尾节点地址是否相同，若相同则一定相交。此时的时间复杂度就是O(M+N)，相较于法一可是优化了太多。

再找出第一个交点

执行完上一步知道了链表相交，接下来就要求交点了，先求出两个链表的长度La，Lb。再定义连个指针分别指向两个链表的头，让长度较长的链表指针先走 | La-Lb | 步，再让两个链表指针一起走，若发现地址存在相同，那么就停止，此时找到交点。这种情况的时间复杂度同样是O(M+N)。

• 代码如下：

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    int lenA = 0;
    int lenB = 0;
    struct ListNode* cur1 = headA;
    struct ListNode* cur2 = headB;
    //1、判断是否相交
    while (cur1->next)
    {
        cur1 = cur1->next;
        lenA++;
    }
    while (cur2->next)
    {
        cur2 = cur2->next;
        lenB++;
    }
    //若相交，进入if判断
    if (cur1 == cur2)
    {
        struct ListNode* shortList = headA, * longList = headB;
        if (lenA > lenB)
        {
            longList = headA;
            shortList = headB;
        }
        int num = abs(lenA - lenB);
        //让长的链表先走差距步
        while (num--)
        {
            longList = longList->next;
        }
        while (shortList && longList)
        {
            if (shortList == longList)
            {
                return shortList;
            }
            //此时两链表一起走
            else
            {
                shortList = shortList->next;
                longList = longList->next;
            }
        }
    }
    //若不相交，则直接返回空
    return NULL;
}

3、复制带随机指针的链表

• 链接直达：

复制带随机指针的链表

• 题目： 思路：

法一：直接复制（malloc）+ 找相对距离

定义一个指针cur指向原链表第一个元素，cur指向第一个值为7，再malloc出一个7来，cur往后走，继续malloc，再尾插，以此遍历下去。新的链表复制出来了，关键在于如何处理新链表的random指针，这里可以采用找相对距离的方法，找原链表random指向第几个，那么新链表对应指向第几个。但是这个方法过于复杂，时间复杂度达到了O(N^2)。不是太推荐

法二：

首先，把拷贝节点链接在原节点后面

struct Node* cur = head;
//1、拷贝节点链接在原节点后面
while (cur)
{
    struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
    copy->val = cur->val;
    copy->next = cur->next;
    cur->next = copy;
    cur = cur->next->next;
}

接着，链接拷贝节点的random在原节点random后面

比如我们拷贝出来的13这个数字，拷贝的13的random就是原头13的random的next 。因为在原链表中，13的random指向7，现在想让拷贝出来的13的random指向拷贝出来的7。原链表中，7的next指向拷贝出的7，综上：拷贝的13的random就是原头13的random的next 。以此类推。

//2、更新拷贝节点的random
cur = head;
while (cur)
{
    struct Node* copy = cur->next;
    if (cur->random == NULL)
    {
        copy->random = NULL;
    }
    else
    {
        copy->random = cur->random->next;
    }
    cur = cur->next->next;
}

最后，恢复原链表，把拷贝链表链接在一起

//3、拷贝节点剪下来，链接到一起
cur = head;
struct Node* copyTail = NULL;
struct Node* copyHead = NULL;
while (cur)
{
    struct Node* copy = cur->next;
    struct Node* next = copy->next;
    cur->next = next;
    if (copyTail == NULL)
    {
        copyHead = copyTail = copy;
    }
    else
    {
        copyTail->next = copy;
        copyTail = copyTail->next;
    }
    cur = next;
}
return copyHead;
}

• 总代码如下：

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur = head;
    //1、拷贝节点链接在原节点后面
    while (cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = cur->next->next;
    }
    //2、更新拷贝节点的random
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    //3、拷贝节点剪下来，链接到一起
    cur = head;
    struct Node* copyTail = NULL;
    struct Node* copyHead = NULL;
    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        cur->next = next;
        if (copyTail == NULL)
        {
            copyHead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }
        cur = next;
    }
    return copyHead;
}