数据结构——链表专题2

一、返回倒数第k 个节点

原题链接：返回倒数第k 个节点

利用快慢指针的方法：先让fast走k步，然后fast和slow一起走，直到fast为空，最后slow指向的结点就是目标结点

int kthToLast(struct ListNode* head, int k)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(k--)
    {
        fast = fast->next;
    }
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、链表的回文结构

原题链接：链表的回文结构

对于这道题，可以分为三个步骤

首先，找到链表的中间结点mid
其次，从中间结点开始将链表逆置
最后，将指向原链表的指针A与指向逆置后的指针rmid的结点数据进行比较，遍历链表

class PalindromeList
{
public:
    //找到中间结点
    struct ListNode* FindMid(struct ListNode* head)
    {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    //逆置链表
    struct ListNode* Reserve(struct ListNode* head)
    {
        struct ListNode* n1 = NULL;
        struct ListNode* n2 = head;
        struct ListNode* n3 = n2->next;
        while(n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3)
            {
                n3 = n3->next;
            }
        }
        return n1;
    }
    bool chkPalindrome(ListNode* A)
    {
        struct ListNode* mid = FindMid(A);
        struct ListNode* rmid = Reserve(mid);
        while(A && rmid)
        {
            if(A->val != rmid->val)
            {
                return false;
            }
            A = A->next;
            rmid = rmid->next;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

三、相交链表

原题链接：相交链表

关于链表的相交，不是交叉形状，而是Y字形

那么如何解决这个问题呢？
可以创建两个指针变量，分别指向各自的头结点，然后遍历找到尾结点并且比较尾结点是否相同，相同就表示两个链表一定相交，不相同直接返回NULL

确定两个链表相交，那么如何找到相交的头结点呢？
鉴于两个链表的长度不一定相等，应该在上述遍历链表的时候记录下各自链表的长度，然后让指向长度大的链表的指针先走差距步，这样两个指针距离相交结点的距离就相等了，直接循环遍历找到目标结点即可

那么哪个链表更长呢？
这里可以用假设法，假设长的为A，后面再判断是否A与B的大小，这样可以省了不少代码量，更加方便

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    struct ListNode* pcurA = headA;
    int lenA = 1;
    struct ListNode* pcurB = headB;
    int lenB = 1;
    while(pcurA->next)
    {
        pcurA = pcurA->next;
        lenA++;
    }
    while(pcurB->next)
    {
        pcurB = pcurB->next;
        lenB++;
    }
    //判断尾结点是否相等
    if(pcurA != pcurB)
    {
        return NULL;
    }
    //假设法
    //假设longnode = headA   shortnode = headB
    int gap = abs(lenA - lenB);
    struct ListNode* longnode = headA;
    struct ListNode* shortnode = headB;
    if(lenA < lenB)
    {
        longnode = headB;
        shortnode = headA;
    }
    //走差距步
    while(gap--)
    {
        longnode = longnode->next;
    }
    while(longnode != shortnode)
    {
        longnode = longnode->next;
        shortnode = shortnode->next;
    }
    return longnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43