141、如何反转链表？判断链表是否是回文链表？如何判断链表相交？.md

141、如何反转链表？判断链表是否是回文链表？如何判断链表相交？

1. 反转链表的步骤如下：

• 新建一个空链表，作为反转后的链表；
• 遍历原链表，将每个节点插入到新链表的头部，即使新节点成为新链表的头节点；
• 返回新链表。 示例代码如下：

Node* reverseList(Node* head) {
    Node* newHead = NULL;
    Node* cur = head;
    while (cur != NULL) {
        Node* next = cur->next;
        cur->next = newHead;
        newHead = cur;
        cur = next;
    }
    return newHead;
}

2.判断链表是否是回文链表的步骤如下：

• 使用快慢指针法，找到链表的中间节点；
• 将链表的后半部分反转；
• 比较前半部分和后半部分是否相同；
• 将后半部分反转回来；
• 返回比较结果。 示例代码如下：

bool isPalindrome(Node* head) {
    if (head == NULL || head->next == NULL) {
        return true;
    }
    Node* slow = head;
    Node* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    Node* newHead = reverseList(slow);
    Node* cur1 = head;
    Node* cur2 = newHead;
    bool res = true;
    while (cur1 != NULL && cur2 != NULL) {
        if (cur1->val != cur2->val) {
            res = false;
            break;
        }
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    reverseList(newHead);
    return res;
}

3.判断链表相交的步骤如下：

• 遍历两个链表，分别得到它们的长度len1和len2；
• 让较长的链表从头开始走len1-len2步，使得两个链表到达相同的位置；
• 同时遍历两个链表，找到第一个相同的节点，即为相交节点；
• 如果两个链表没有相交，则返回NULL；
• 返回相交节点。 示例代码如下：

Node* getIntersectionNode(Node* headA, Node* headB) {
    int len1 = 0, len2 = 0;
    Node* cur1 = headA;
    Node* cur2 = headB;
    while (cur1 != NULL) {
        len1++;
        cur1 = cur1->next;
    }
    while (cur2 != NULL) {
        len2++;
        cur2 = cur2->next;
    }
    cur1 = headA;
    cur2 = headB;
    int diff = abs(len1 - len2);
    if (len1 > len2) {
        while (diff-- > 0) {
            cur1 = cur1->next;
        }
    } else {
        while (diff-- > 0) {
            cur2 = cur2->next;
        }
    }
    while (cur1 != NULL && cur2 != NULL) {
        if (cur1 == cur2) {
            return cur1;
        }
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return NULL;
}