- 反转链表
- 两两交换链表中的节点
- 删除倒数第n节点
c语言* &
int* q 跟int *q没有区别
# # Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
"""虚拟节点"""
ihead = ListNode(next=head)
"""虚拟节点起始位置用于指示当前位置前一位置"""
ip = ihead
"""当前位置的下一位置"""
p = ip.next
while p is not None:
"""p不为None节点，判断是否与val相等"""
if p.val == val:
"""相等则删除此节点"""
p = p.next
ip.next = p
else:
ip = ip.next
p = p.next
return ihead.next #这里是虚拟头节点的下一个 可以避免下面一种情况
none null区别
链表细节太多了
细节1: 头节点定义
细节2:addtail 跟add head方法复用addindex
细节3:这个index 到底应该如何去判断？
从0开始 但是 for i in range(0) 并不会进入循环 所以index 需要➕1 ！
细节4:index < 0 index> 长度 index< 长度
画出流程图是一个好方法
反转链表迭代法
class Node:
def __init__(self, val): # self,val 不然不能用Node(val)来初始化
self.val = val
self.next = None
class MylinkedList(object):
def __init__(self):
self.head = Node(0) # 然后这里是一个头节点 这个类是定义的单节点！！类中没办法再定义类！！
def get(self, index):
"""
:type index: int
:rtype: int
"""
"""指针p"""
if index < 0:
return -1
p = self.head
for i in range(index + 1):
if p.next is not None:
p = p.next
if i == index:
return p.val
else:
return -1
def addAtHead(self, val):
"""
:type val: int
:rtype: None
"""
"""指针p"""
p = self.head
# 如果没有定义这样一个类 你都没办法赋值！
new = Node(val)
new.next = p.next
p.next = new
print(new.val)
def addAtTail(self, val):
"""
:type val: int
:rtype: None
"""
p = self.head
while p.next:
p = p.next
new = Node(val)
p.next = new
def addAtIndex(self, index, val):
"""
:type index: int
:type val: int
:rtype: None
"""
"""指针"""
p = self.head
np = p.next
if index < 0:
new = Node(val)
new.next = p.next
p.next = new
else:
for i in range(index + 1):
"""i这个位置有没有结点"""
if np is not None:
if i == index:
new = Node(val)
new.next = np
p.next = new
else:
p = p.next
np = np.next
else:
if i == index:
new = Node(val)
p.next = new
else:
return -1
def deleteAtIndex(self, index):
"""
:type index: int
:rtype: None
"""
"""头节点p"""
p = self.head
np = p.next
for i in range(index + 1):
if np is not None:
if i == index:
p.next = np.next
else:
p = p.next
np = np.next
else:
if i == index:
p.next = None
else:
break
# opt = MylinkedList()
# opt.addAtHead(2)
# opt.deleteAtIndex(1)
# p = opt.head
# p = p.next
# print(p.val)
递归法
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
# self.reverseList(head.next) # 这一步错了
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p # 为什么返回的是p 因为p就是末尾！ 不需要进行什么操作 一直返回就行！
两两交换链表中的节点
迭代法
- next太多下 花太多时间
- 没有返回“头”结点
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dhead = ListNode(0)
dhead.next = head
temp = dhead
while temp.next and temp.next.next:
node1 = temp.next
node2 = temp.next.next
temp.next = node2
node1.next = node2.next
node2.next = node1
temp = node1
return dhead.next# 忘记返回头节点！头结点变到后面去了！！！
递归法
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None: #这里的判断是有顺序的
return head
newhead = head.next
head.next = self.swapPairs(newhead.next)
newhead.next = head
return newhead
删除倒数第n节点
暴力法
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
size = 0
dh = ListNode(0)
dh.next = head
p = dh
while p.next:
p = p.next
size += 1
t = size - n + 1
count = 0
p = dh
while count < t - 1:
p = p.next
count += 1
p.next = p.next.next
return dh.next # 万一删除的是头结点呢！所以不能是return head
栈法
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
stack = list()
dhead = ListNode(0,head)
cur = dhead
while cur:
stack.append(cur)
cur = cur.next
for i in range(n):
stack.pop()
prev = stack.pop()
prev.next = prev.next.next
return dhead.next
双指针法
a 比 b 超前n 个节点！！！！
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
dhead = ListNode(0)
dhead.next = head
f = dhead
l = dhead
for i in range(n+1):
l = l.next
while l:
f = f.next
l = l.next
f.next = f.next.next
return dhead.next
