首页 > 其他 > 详细

Leetcode Intersection of Two Linked Lists

时间:2014-12-16 20:53:09      阅读:271      评论:0      收藏:0      [点我收藏+]
/**
 * 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) {
        int lena = count(headA);
        int lenb = count(headB);
        int diff = 0;
        ListNode* longer = NULL;
        ListNode* shorter= NULL;
        if (lena > lenb) {
            diff = lena - lenb;
            longer = headA;
            shorter= headB;
        } else {
            diff = lenb - lena;
            longer = headB;
            shorter= headA;
        }
        longer = forward(longer, diff);
        
        while (longer != shorter) {
            longer = forward(longer, 1);
            shorter= forward(shorter, 1);
        }
        return longer;
    }
    ListNode* forward(ListNode* head, int step) {
        while(head != NULL) {
            if (step-- <= 0) {
                break;
            }
            head = head->next;
        }
        return head;
    }
    int count(ListNode* head) {
        int res = 0;
        while (head != NULL) {
            head = head->next;
            res++;
        }
        return res;
    }
};

Leetcode 也有可视化了,越来越高端了

Leetcode Intersection of Two Linked Lists

原文:http://www.cnblogs.com/lailailai/p/4167864.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!