SpringBoot怎么找出兩個單鏈表的交叉節點

這篇文章主要講解了“SpringBoot怎么找出兩個單鏈表的交叉節點”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“SpringBoot怎么找出兩個單鏈表的交叉節點”吧！

題目：寫一個程序找出兩個單鏈表的交叉節點。
思路：單鏈表A和單鏈表B，交叉點后的部分是一樣的，也就是說長度是一樣的，如上所示：c1 → c2 → c3。所以，將單鏈表A和單鏈表B相差的部分去掉，依次對應比較等長的部分即可。在計算兩個鏈表的長度之后，比較兩個鏈表的尾節點是否一樣，如果不一樣說明沒有交叉節點，返回NULL。

Language : c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curA = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode *curB = (struct ListNode*)malloc(sizeof(struct ListNode));
    curA = headA;
    curB = headB;int length_a = 1;int length_b = 1;int i = 0;if(curA == NULL || curB == NULL){return NULL;
    }while(curA->next != NULL){
        curA = curA->next;
        length_a++;
    }while(curB->next != NULL){
        curB = curB->next;
        length_b++;
    }if(curA != curB){return NULL;
    }
    curA = headA;
    curB = headB;if(length_a > length_b){for(i; i < length_a-length_b; i++){
            curA = curA->next;
        }
        i = 0;
    }else if(length_a < length_b){for(i; i < length_b-length_a; i++){
            curB = curB->next;
        }
        i = 0;
    }while(curA != curB){
        curA = curA->next;
        curB = curB->next;
    }return curA;
}

Language : cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * }; */class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA, *curB;
        curA = headA;
        curB = headB;if(curA == NULL || curB == NULL){return NULL;
        }int length_a = getLength(curA);int length_b = getLength(curB);if(length_a > length_b){for(int i=0; i < length_a-length_b; i++){
                curA = curA->next;
            }
        }else if(length_a < length_b){for(int i=0; i < length_b-length_a; i++){
                curB = curB->next;
            }
        }while(curA != curB){
            curA = curA->next;
            curB = curB->next;
        }return curA;
    }
private:int getLength(ListNode *head){int length = 1;while(head->next != NULL){
            head = head->next;length++;
        }return length;
    }
};

Language：python

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):def getIntersectionNode(self, headA, headB):"""
        :type head1, head1: ListNode
        :rtype: ListNode
        """if headA is None or headB is None:return Nonepa = headA # 2 pointerspb = headBwhile pa is not pb:# pa先遍歷headA，然后再遍歷headB# pb先遍歷headB，然后再遍歷headApa = headB if pa is None else pa.next
            pb = headA if pb is None else pb.nextreturn pa # 只有兩種方式結束循環，一種是pa和pb所指相同，另一種是headA和headB都已經遍歷完仍然沒有找到。

感謝各位的閱讀，以上就是“SpringBoot怎么找出兩個單鏈表的交叉節點”的內容了，經過本文的學習后，相信大家對SpringBoot怎么找出兩個單鏈表的交叉節點這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！