h5网站开发中心,建设部网人事考试网站,网站建设需要懂什么软件,软件开发招聘链表节点的定义链表作为一种数据结构#xff0c;由链表节点互相连接构成。链表节点包含自身的数据和一个指向下一节点的指针。
Definition of ListNodeclass ListNode(object):def __init__(self, val, nextNone):self.val valself.ne…链表节点的定义链表作为一种数据结构由链表节点互相连接构成。链表节点包含自身的数据和一个指向下一节点的指针。
Definition of ListNodeclass ListNode(object):def __init__(self, val, nextNone):self.val valself.next next由于节点自身的结构特点链表可以仅由一个头结点表示。环形链表顾名思义环形链表指链表构建过程中存在环即链表中某一节点从自身出发最后可以访问到自身。判断链表是否为环形链表leecode141 LinkedListCycle这题只需记住快慢指针。至于中间的判断条件再慢慢debug。class Solution:param head: The first node of linked list.return: True if it has a cycle, or falsedef hasCycle(self, head):if head is None:return False# 快慢指针快的走两步慢的走一步fast headslow headwhile(fast.next and fast.next.next):fast fast.next.nextslow slow.nextif fast slow:return Truereturn False查找环形链表的入口leetcode142 LinkedListCycleII在快慢指针的基础上如果快慢指针重合将快慢指针恢复成单步指针x,z让x指针从头开始z指针从重合位置开始当x、z指针再次相遇即为环形链表的入口Y。这可以通过理论证明感兴趣搜一下。class Solution(object):def detectCycle(self, head)::type head: ListNode:rtype: ListNodefast headslow headwhile(fast.next and fast.next.next):fast fast.next.nextslow fast.nextif fast slow:breakif fast is None:return Nonefast headwhile(fast ! slow):fast fast.nextslow slow.nextreturn slow相交链表除了在单独一条环形链表找节点入口还有一种情况是求解两条相交链表的入口。leetcode160 getIntersectionNode这题理论分析上简单一点。假设链表1长度ac,链表2长度bc),姑且ab若同时遍历x节点在链表1走到尾时y节点在链表2距离尾(b-a) 这时使走到尾的x节点从链表2头开始y节点在链表2走到尾时x在链表2头已经走了b-a)个节点。此时然y节点在链表1头开始同时单步移动x、y节点由于x节点比y节点多走了b-a下次首次相遇一定是在两链表的交点。class Solution(object):def getIntersectionNode(self, headA, headB)::type headA, headB: ListNode:rtype: ListNode# 算出长链表比短链表多的长度让长链表多走k步if headA is None or headB is None:return NonetmpA headAtmpB headBlenA 0lenB 0while(tmpA):tmpA tmpA.nextlenA 1while(tmpB):tmpB tmpB.nextlenB 1if lenA lenB:for i in range(lenA - lenB):headA headA.nextelse:for i in range(lenB - lenA):headB headB.nextwhile(headA ! headB):headA headA.nextheadB headB.nextreturn headA更多精彩文章欢迎关注公众号“Li的白日呓语”。
