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 的大作中提到】
: 不是数组，呵呵，
: 怎么作比较好？把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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: In my opinion, unless explicitly specified, almost all interview problems refer linked list as singly linked list.
|
