原理:检查一个链表是不是分叉链表,将两个头分别记录,然后看看这两个链表的长度,如果不一样就直接将长的先走long-short个结点,然后同时走,如果走的时候发现下一个结点相同的话,那么就是分叉链表
//分叉链表 SListNode * getIntersectionNode(SList* listA, SList* listB) { int lenA = 0; int lenB = 0; SListNode * cur; SListNode * headlong = listA->_head; SListNode * headshort = listB->_head; int gap; int i; for (cur = listA->_head; cur; cur = cur->_next) { lenA++; } for (cur = listB->_head; cur; cur = cur->_next) { lenB++; } gap = lenA - lenB; if (gap < 0) { gap *= -1; headshort = listA->_head; headlong = listB->_head; } for (i = 0; i < gap; i++) { headlong = headlong->_next; } for (; headlong; headlong = headlong->_next, headshort = headshort->_next) { if (headlong == headshort) { return headlong; } } return NULL; }