[leetcode]初级算法——链表
程序员文章站
2024-03-06 21:21:14
...
删除链表中的节点
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Example:
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list
should become 4 -> 1 -> 9 after calling your function.
Code(By myself):
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next
return
Code(others):
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
if (not node) or (not node.next):
return
node.val = node.next.val
node.next = node.next.next
总结:
覆盖掉该节点
删除链表中的节点
Given a linked list, remove the n-th node from the end of list and return its head.Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Code(By myself):
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
p = head
q = head
while n:
q = q.next
n -= 1
if q == None:
head = head.next
while q != None and q.next != None:
p = p.next
q = q.next
if p.next == None:
head = None
else:
p.next = p.next.next
return head
Code(others):class Solution:
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
if not head:
return None
first, second = head, head
for i in range(n):
if not first.next:
return head.next
first = first.next
while first.next:
first = first.next
second = second.next
second.next = second.next.next
return head
总结:
学会优化代码
反转链表
Reverse a singly linked list.Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Code(By myself):
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
p = head
if p == None or p.next == None:
return head
q = head.next
if q.next == None:
p.next = None
q.next = p
head = q
return head
o = q.next
while o != None:
q.next = p
p = q
q = o
o = o.next
q.next = p
head.next = None
head = q
return head
Code(others):class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
new_head=None
while head:
p=head
head=head.next
p.next=new_head
new_head=p
return new_head
总结:
循环里的每一步都整理出来代码能更简洁
合并两个有序链表
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Code(By myself):
class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
p = ListNode(0)
head = p
while l1 and l2:
if l1.val < l2.val:
p.next = l1
p = l1
l1 = l1.next
else:
p.next = l2
p = l2
l2 =l2.next
if l1:
p.next = l1
if l2:
p.next = l2
return head.next
回文链表
Given a singly linked list, determine if it is a palindrome.Example:
Input: 1->2
Output: false
Code(By myself):
class Solution:
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
p = head
list = []
while p:
list.append(p.val)
p = p.next
list.reverse()
p = head
for i in range(len(list)//2):
if p.val != list[i]:
return False
p = p.next
return True
环形链表
Given a linked list, determine if it has a cycle in it.Code(By myself):
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
Code(others):class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
curr = head
while curr is not None:
nextnode = curr.next
if nextnode is head:
return True
curr.next = head
curr = nextnode
return False
总结:将节点next指向head形成一种标记
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
上一篇: Android时分秒计时器的两种实现方法