今天是day4
第一题：两两交换链表中的节点：
func swapPairs(head *ListNode) *ListNode {
dummy:=&ListNode{
Next:head
}
pre:=dummy
for head!=nil && head.Next!=nil{
pre.Next = head.Next
next:=head.Next.Next
head.Next.Next = head
head.Next = next
pre = head
head = next
}
return dummy.Next
}
go递归法：
func swapPairs(head *ListNode) *ListNode{
if head == nil || head.Next!=nil{
return head
}
next:=head.Next
head.Next = sawpPairs(next.Next)
next.Next = head
return next
}
python版本：
class Solution:
def swapPairs(self,head: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = ListNode(next =head)
current = dummy_head
while current.next and current.next.next:
temp = current.next
temp1 = current.next.next.next
current.next = current.next.next
current.next.next = temp
temp.next = temp1
curernt = current.next.next
return dummy_head.next
python递归：
class Solution:
def swapPairs(self,head:Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
pre = head
cur = head.next
next = head.next.next
cur.next = pre
pre.next = self.swapPairs(next)
return cur
题二：删除链表倒数第N个元素:
func removeFromend(head *ListNode,n int) *ListNode{
dummy_node := &ListNode{0,head}
fast,slow:=dummy_node,dummy_node
for i:=0;i<=n;i++{
fast = fast.Next
}
for fast!=nil{
slow = slow.Next
fast = fast.Next
}
slow.Next = slow.Next.Next
return dummy_node.Next
}
python版本：
class Solution:
def removefrom(self,head:Optional[ListNode],n int) -> Optional[ListNode]:
dummy_node = ListNode{0,head}
slow = fast = dummy_node
for i in range(n+1):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy_node.next
题目三：判断链表相交的点并输出位置
func getIntersec(headA,headB *ListNode) *ListNode{
cura := headA
curb := headB
lena :=0
lenb :=0
for cura!=nil{
cura = cura.Next
lena++
}
for curb !=nil{
curb = curb.Next
lenb++
}
var step int
var fast,slow *ListNode
if lena > lenb {
step = lena - lenb
fast,slow = headA,headB
}else {
step = lenb - lena
fast,slow = headB,headA
}
for i:=0;i<step;i++{
fast = fast.next
}
for fast!=slow{
fast = fast.Next
slow = slow.Next
}
return fast
}
go双指针法:
func getintersec(haedA,headB *ListNode) *ListNode {
l1,l2:=headA,headB
for l1!=l2{
if l1 != nil{
l1 = l1.Next
}else{
l1 = headB
}
if l2!=nil{
l2 = l2.Next
}else{
l2 = headA
}
}
return l1
}
python实现：
class Solution:
def getIntersec(self,headA:ListNode,headB:ListNode) -> Optional[ListNode]:
lena,lenb = 0,0
cur = headA
while cur:
cur = cur.next
lena+=1
cur = headB
while cur:
cur = cur.next
leb+=1
cura,curb = headA,headB
if lena > lenb:
cura,curb = curb,cura
lena,lenb = lenb,lena
for _ in range(lenb - lena):
curb = curb.next
while cura:
if cura == curb:
return cura
else:
cura = cura.next
curb = curb.next
return None
法二：
class Solution:
def getinserct(self,headA:ListNode,headB:ListNode) ->Optional[ListNode]:
if not headA or not headB:
return None
pointera = headA
pointerb = headB
while pointera!=pointerb:
pointera = pointera.next if pointera else headB
pointerb = pointerb.next if pointerb else headA
return pointera
题目四：环形链表，判断链表内是否有环并输出入环的第一个节点：
func detecCycle(head *ListNode) *ListNode{
slow,fast:=head,head
for fast!=nil && fast.Next !=nil{
slow = slow.Next
fast = fast.Next.Next
if slow == fast{
for slow !=head{
slow = slow.Next
head = head.Next
}
return head
}
}
return nil
}
python版本：
class Solution:
def detectcycle(self,head:Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while fast and fast.next:
slow= slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow!=fast:
slow = slow.next
fast = fast.next
return slow
return None