C++相交链表和反转链表详解

相交链表

相交链表即链表两个节点开始重合，即它们的next指针指向同一个节点。我们可以通过以下两种方法实现相交链表的查找：

1.暴力法

这是一种比较直接的方法，即双层for循环，分别遍历两个链表，找到首个指针相同的节点即为相交节点。时间复杂度为O(mn)。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    while (headA) {
        ListNode *p = headB;
        while (p) {
            if (headA == p) return headA;
            p = p->next;
        }
        headA = headA->next;
    }
    return nullptr;
}

2.双指针法

在双指针法中，我们分别遍历两个链表并计算它们的长度，然后对长链表的指针进行偏移，使两个链表的连结点到达同一位置之后进行遍历，查找到首个指针相同的节点即为相交节点。时间复杂度为O(m+n)。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = calLength(headA), lenB = calLength(headB);
    int k = abs(lenA - lenB);
    if (lenA > lenB) while (k--) headA = headA->next;
    else if (lenB > lenA) while (k--) headB = headB->next;
    while (headA && headB) {
        if (headA == headB) return headA;
        headA = headA->next;
        headB = headB->next;
    }
    return nullptr;
}

int calLength(ListNode *head) {
    int cnt = 0;
    while (head) {
        cnt++;
        head = head->next;
    }
    return cnt;
}

反转链表

反转链表是指将链表中的指针方向从原来的单向改为反向，即一个节点的指针指向它前面的节点。以下是一种常用的递归方法：

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

以下是一种迭代方法：

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr;
    while (head) {
        ListNode *temp = head->next;
        head->next = prev;
        prev = head;
        head = temp;
    }
    return prev;
}

示例说明

相交链表

假设现在有两个链表，分别为：

链表1: 1 -> 2 -> 3 -> 4 -> 5 -> 6，并且其尾部指向节点3；

链表2: 7 -> 8 -> 3 -> 4 -> 5 -> 6。

这两个链表相交于节点3，我们想要编写一个程序，通过代码得到它们的交点。

使用暴力法，代码如下：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    while (headA) {
        ListNode *p = headB;
        while (p) {
            if (headA == p) return headA;
            p = p->next;
        }
        headA = headA->next;
    }
    return nullptr;
}

使用双指针法，代码如下：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = calLength(headA), lenB = calLength(headB);
    int k = abs(lenA - lenB);
    if (lenA > lenB) while (k--) headA = headA->next;
    else if (lenB > lenA) while (k--) headB = headB->next;
    while (headA && headB) {
        if (headA == headB) return headA;
        headA = headA->next;
        headB = headB->next;
    }
    return nullptr;
}

int calLength(ListNode *head) {
    int cnt = 0;
    while (head) {
        cnt++;
        head = head->next;
    }
    return cnt;
}

反转链表

链表：1 -> 2 -> 3 -> 4 -> 5，我们想要将这个链表反转。使用迭代法，代码如下：

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr;
    while (head) {
        ListNode *temp = head->next;
        head->next = prev;
        prev = head;
        head = temp;
    }
    return prev;
}

使用递归法，代码如下：

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}