C**********n 发帖数: 100 | 1 不是数组,呵呵,
怎么作比较好?把linked list转换成数组再作是不是不符合出题人的意思? |
g*******y 发帖数: 1930 | 2 reverse only half
compare
reverse back |
m********0 发帖数: 2717 | 3 only one traverse?
without knowing the length?
【在 C**********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是数组,呵呵, : 怎么作比较好?把linked list转换成数组再作是不是不符合出题人的意思?
|
g*******y 发帖数: 1930 | 4 one traversal is impossible. Just iterate to the end will take you 1
traversal.
My optimal two and half times of traversal (well, the constant factor for
low-level instructions will be larger than 2.5 for sure)
【在 m********0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : only one traverse? : without knowing the length?
|
m********0 发帖数: 2717 | 5 of course possible for double linked list giving the length.
without length and single linked.
find the length
reverse the second half
traverse from both sub-list
trivial
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : one traversal is impossible. Just iterate to the end will take you 1 : traversal. : My optimal two and half times of traversal (well, the constant factor for : low-level instructions will be larger than 2.5 for sure)
|
g*******y 发帖数: 1930 | 6 In my opinion, unless explicitly specified, almost all interview problems refer linked list as singly linked list.
【在 m********0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : of course possible for double linked list giving the length. : without length and single linked. : find the length : reverse the second half : traverse from both sub-list : trivial
|
m********0 发帖数: 2717 | 7 xiao wei yang, ni de dao le ta.
refer linked list as singly linked list.
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : In my opinion, unless explicitly specified, almost all interview problems refer linked list as singly linked list.
|