相交链表
160. 相交链表 - 力扣(LeetCode) (leetcode-cn.com)
- 获取两个链表的长度,并判断两个链表最后节点地址是否相同。
- 相同–较长的链表减去长度差。
- 同时递减,获取相同地址的节点。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if(headA == NULL || headB == NULL) return NULL; int cutA = 0; int cutB = 0; struct ListNode *tailA = headA; struct ListNode *tailB = headB; // 1. 获取两个链表的长度,并判断两个链表最后节点地址是否相同。 while(tailA->next != NULL) { cutA++; tailA = tailA->next; } while(tailB->next != NULL) { cutB++; tailB = tailB->next; } if(tailA != tailB) return NULL; // 2. 相同--较长的链表减去长度差。 // int dif = abs(cutA -cutB); int dif = cutA > cutB ? (cutA - cutB) : (cutB - cutA); struct ListNode *Lhead = headA; struct ListNode *Shead = headB; if(cutB > cutA) { Lhead = headB; Shead = headA; } while(dif--) { Lhead = Lhead->next; } // 3. 同时递减,获取相同地址的节点。 while(Lhead != Shead && Lhead != NULL && Shead != NULL) { Lhead = Lhead->next; Shead = Shead->next; } return Lhead; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)