数据结构初阶（2）——链表OJ

目录

1.面试题 02.02. 返回倒数第 k 个节点

2.OR36 链表的回文结构

3.160. 相交链表

1.面试题 02.02. 返回倒数第 k 个节点

思路：快慢指针，快指针先走k格，慢指针同步

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


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

2.OR36 链表的回文结构

思路：先找中间节点，然后将节点后逆置，最后一一比较

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    struct ListNode* middleNode(struct ListNode* head)
    {
   struct ListNode* slow=head,*fast=head;
   while(fast&&fast->next)
   {
    slow=slow->next;
    fast=fast->next->next;
   }
   return slow;
    }
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode* cur=head;
        struct ListNode* newhead=NULL;
        while(cur)
        {
            struct ListNode*next=cur->next;
            cur->next=newhead;
            newhead=cur;
            cur=next;
        }
        return newhead;
    }
    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid=middleNode(A);
        struct ListNode* rmid=reverseList(mid);
        while(rmid&&A)
        {
            if(rmid->val!=A->val)
            return false;
            rmid=rmid->next;
            A=A->next;
        }
       return true;
    }
};

3.160. 相交链表

思路：先判断是否相交，再计算长度差值，再一一比较

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* cura=headA,*curb=headB;
    int lena=1,lenb=1;
    while(cura->next)
    {
        cura=cura->next;
        lena++;
    }
    while(curb->next)
    {
        curb=curb->next;
        lenb++;
    }
    if(cura!=curb)
    {
        return NULL;
    }
    int gap=abs(lena-lenb);
    struct ListNode* long1=headA,*short1=headB;
    if(lenb>lena)
    {
        long1=headB;
        short1=headA;
    }
    while(gap--)
    {
        long1=long1->next;
    }
    while(long1!=short1)
    {
        long1=long1->next;
        short1=short1->next;
    }
    return long1;
}