程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode從零單刷]Intersection of Two Linked Lists

[LeetCode從零單刷]Intersection of Two Linked Lists

編輯:關於C++

題目:

 

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.The linked lists must retain their original structure after the function returns.You may assume there are no cycles anywhere in the entire linked structure.Your code should preferably run in O(n) time and use only O(1) memory.

解答:

需要的是常量級別的空間,而且時間是遍歷的時間(可以常數次的多次遍歷)。

因為是單鏈表,所以沒辦法從尾部開始回搜到第一個不相同的節點。那能不能從頭部開始搜到第一個相同的節點?

好像不行,因為鏈表的長度各不相同。如果是長度相同的鏈表就可以了。我們截掉更長的鏈表的頭幾個多余元素。

如果我可以知道兩者的鏈表長度,長度通過遍歷鏈表得到。

 

/**
 * 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* ha = headA;
        ListNode* hb = headB;
        int lenA = 0;
        int lenB = 0;
        
        while(ha != NULL) {ha = ha->next; lenA++;}
        while(hb != NULL) {hb = hb->next; lenB++;}
        ha = headA;
        hb = headB;
        
        if(lenA > lenB) {
            int diff = lenA - lenB;
            while(diff--)   ha = ha->next;
        }
        
        if(lenB > lenA) {
            int diff = lenB - lenA;
            while(diff--)   hb = hb->next;
        }
        
        while(ha) {
            if(ha == hb)    return ha;
            ha = ha->next;
            hb = hb->next;
        }
        return NULL;
    }
};

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved