单链表的应用（3）

返回倒数第k个结点

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

思路：

1. 利用快慢指针，先让快指针走k步
2. 快慢指针一起往后遍历，直到快指针到达链表的末端
3. 此时的慢指针就是链表的倒数第k个结点

int kthToLast(struct ListNode* head, int k)
{
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    while(k--)
    {
        fast=fast->next;
    }//快指针先走k步
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }//快慢指针同时进行遍历
    return slow->val;
}

链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

思路：

1. 利用快慢指针寻找中间结点
2. 将中间结点之后的结点进行倒置
3. 从链表的两端进行遍历，判断结点是否相等，直到尾结点遍历到NULL

class PalindromeList {
public:
    ListNode* FindMid(ListNode* A)
    {
        ListNode* slow=A;
        ListNode* fast=A;
        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }//找中间结点

    ListNode* reverseList(ListNode* A)
    {
        ListNode* n1,*n2,*n3;
        n1=NULL;
        n2=A;
        n3=A->next;
        while(n2)
        {
            n2->next=n1;
            n1=n2;
            n2=n3;
            if(n3)
                n3=n3->next;
        }
        return n1;
    }//中间结点后的结点进行倒置

    bool chkPalindrome(ListNode* A) {
        ListNode* mid=FindMid(A);
        ListNode* right=reverseList(mid);
        ListNode*left=A;
        while(right)
        {
            if(left->val != right->val)
                return false;
            left=left->next;
            right=right->next;
        }
        return true;
    }//遍历判断是否为回文结构
};

相交结点

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

思路：

1. 分别遍历两个链表，计算两个链表的长度
2. 若两个链表长度不相等，则将长的链表走两个链表的差值，使两个链表在遍历时能够同时到达链表的末端
3. 遍历两个链表，若两个链表相等时，则返回任意一个链表的该结点，若到两链表遍历结束都未出现相同结点，则返回NULL；

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *pcur1=headA;
    struct ListNode *pcur2=headB;
    int i=0;
    int j=0;
    while(pcur1)
    {
        i++;
        pcur1=pcur1->next;
    }
    while(pcur2)
    {
        j++;
        pcur2=pcur2->next;
    }//计算两个链表长度
    int gap=abs(i-j);
    struct ListNode *longlist=headA;
    struct ListNode *shortlist=headB;
    if(i < j)
    {
        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;
}