算法-链表区域反转

j

k

cur.Next := temp.Next

temp.Next = pre.Next

temp = cur.Next

f

e

d

c

m=3       n=8

1. cur链表不变，仍为cur[0]+c[2:]2. temp链表不变，仍为temp[0]+pre[1:]3. pre|dummy链表都变为，首串+cur[1]+curfont color=\"#e74f4c\

pre第一次循环后

a

b

g

h

temp.Next

temp.Next = pre.Next

End

temp

轮次M+1

处理前：arr

pre.Next

轮次  M此例中：M=3

3. 将cur[1]元素放置到pre.Next的首位

temp      := cur.Next

pre.Next = 待反转子串+尾部子串

n-m-1次循环后

期望结果：

pre

注意：此时temp链表未发生变化

1. cur|pre|dummy链表未发生变化2. temp链表变为temp[0]+pre[1:]

pre.Next = temp

temp.Next = pre.Next

pre.Next = temp

待反转子串

1. 暂存未处理元素

cur

1. cur链表不变，仍为cur[0]+c[2:]2. temp链表不变，仍为temp[0]+pre[1:]3. pre|dummy链表都变为，span style=\

思路        首子串startArr={a，b} 与 尾子串endArr={j，k} 保持不变；        将 待反转子串reverseArr 中，从第二个元素（d）起，每次循环将此元素插入到首子串starArr之后;        即，使用一个起始长度为reverseArr.len-1的窗口tempArr，每次循环将tempArr首元素取出，并插入至reverseArr开头，直至tempArr为空结束循环（span style=\"font-size:inherit;\

x

轮次   1~(M-1)此例中：轮次为1-2

1. cur|pre|dummy链表移除了元素e2. temp链表未发生变化

temp      := cur.Next

3. 将cur[1]元素放置到pre.Next的首位

第7轮

链表：arr

cur.Next := temp.Next

反转范围：

pre := pre.Next

轮次2

虚拟头

2. 移除cur[1]元素

pre第二次循环后

第4轮

1. cur|pre|dummy链表移除了元素d2. temp链表未发生变化

cur下一跳由d变为e

指针位置

c下一跳由e变为f

数据定义

3. 将cur[1]元素放置到pre.Next的首位

已完成数据

轮次 N-1

temp.Next = pre.Next

1. cur|pre|dummy链表移除了元素h2. temp链表未发生变化

题目地址：https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c

轮次1

pre起始值

1. cur链表不变，仍为cur[0]+c[2:]2. temp链表不变，仍为temp[0]+pre[1:]3. pre|dummy链表都变为，span style=\

temp := cur.Next

4. 拼接     首串       +  pre.Next

c下一跳由h变为j