单链表中的第m和n之间元素反转
m = 2,n = 4
具体做法:
- step 1:我们可以在链表前加一个表头,后续返回时去掉就好了,因为如果要从链表头的位置开始反转,在多了一个表头的情况下就能保证第一个节点永远不会反转,不会到后面去。
-
res = ListNode(-1)
res.next = head
-
res = ListNode(-1)
res.next = head
- step 2:使用两个指针,一个指向当前节点,一个指向前序节点。
-
#前序节
pre = res
#当前节点
cur = head
-
#前序节
pre = res
#当前节点
cur = head
- step 3:依次遍历链表,到第m个的位置。
-
for i in range(1,m):
pre = cur
cur = cur.next
-
for i in range(1,m):
pre = cur
cur = cur.next
- step 4:对于从m到n这些个位置的节点,依次断掉指向后续的指针,反转指针方向。
-
for i in range(m, n):
temp = cur.next
cur.next = temp.next
temp.next = pre.next
pre.next = temp
得到-1—>1—>3—>2—>4—>5—>6
得到-1—>1—>4—>3—>2—>5—>6
-
for i in range(m, n):
temp = cur.next
cur.next = temp.next
temp.next = pre.next
pre.next = temp
- step 5:返回时去掉我们添加的表头
return res.next
def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode: # write code here #加个表头 res = ListNode(-1) res.next = head #前序节点 pre = res #当前节点 cur = head #找到m for i in range(1,m): pre = cur cur = cur.next #从m反转到n for i in range(m, n): temp = cur.next cur.next = temp.next temp.next = pre.next pre.next = temp #返回去掉表头 return res.next 标签:pre,单链,cur,temp,python,反转,表头,next,res From: https://www.cnblogs.com/ailie/p/16940700.html