链表算法实战：相交节点查找与回文结构判断 | 极客日志

链表算法实战：相交节点查找与回文结构判断 | 极客日志

/**
 * 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* pa = headA;
    ListNode* pb = headB;
    int sizeA = 0, sizeB = 0;

    // 循环求长度
    while(pa) {
        sizeA++;
        pa = pa->next;
    }
    while(pb) {
        sizeB++;
        pb = pb->next;
    }

    // 长度差值，使用绝对值函数
    int gap = abs(sizeA - sizeB);

    // 判断链表的长短
    ListNode* longlist = headA;
    ListNode* shortlist = headB;
    if(sizeA < sizeB) {
        longlist = headB;
        shortlist = headA;
    }

    // 长链表先走 gap 步
    while(gap--) {
        longlist = longlist->next;
    }

    // 同时遍历
    while(longlist) {
        // 节点相同
        if(longlist == shortlist) {
            return longlist;
        }
        // 节点不同
        longlist = longlist->next;
        shortlist = shortlist->next;
    }

    // 没有相同的节点
    return NULL;
}

/* 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 index = 0;
        while(pcur){
            arr[index++] = pcur->val;
            pcur = pcur->next;
        }
        // 创建左右指针，双方向遍历数组比较
        int left = 0;
        int right = index - 1;
        while(left < right){
            if(arr[left] != arr[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/
class PalindromeList{
public:
    // 找到中间节点
    ListNode* middleNode(struct ListNode* head){
        // 创建快慢指针
        ListNode* fast,*slow;
        // 首先都指向头节点
        fast = head;
        slow = head;
        // 循环条件将两种情况都包含
        while(fast !=NULL && fast->next !=NULL){
            // 慢指针移动一节点
            slow = slow->next;
            // 快指针移动两个节点
            fast = fast->next->next;
        }
        // 返回 slow
        return slow;
    }

    // 从中间节点开始反转链表
    ListNode* reverseList(struct ListNode* head){
        // 创建三个指针
        ListNode* n1,* n2,* n3;
        // 链表为空
        if(head ==NULL){
            return head;
        }
        // 链表不为空
        // 首先 n1 指向空
        n1 =NULL; n2 = head; n3 = n2->next;
        while(n2){
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            // 当 n2 到达尾节点时，n3 为空，不能对空指针解引用
            if(n3){
                n3 = n3->next;
            }
        }
        return n1;
    }

    bool chkPalindrome(ListNode* A){
        // 找到中间节点
        ListNode* mid = middleNode(A);
        // 从中间节点开始反转
        ListNode* right = reverseList(mid);
        // 遍历原链表和反转之后的链表比较值是否相等
        ListNode* left = A;
        while(right){
            if(right->val != left->val){
                return false;
            }
            right = right->next;
            left = left->next;
        }
        return true;
    }
};