学步园

Suppose there're odd number of elements in a linked-list, how to get the middle element in it? I find a clever way to achieve this on internet. Two pointers point to the linked-list. One is slow pointer and the other is quick pointer. Each time slow pointer moves one step, while the quick pointer moves two steps. When the quick pointer reaches the end of the list, the slow pointer is pointing to the middle of the list.

The slow and quick pointers solution can also be used to check whether there's a loop in linked list in O(n) time. If quick pointer reaches slow pointer somewhere sometime, it means there's a loop in linked list.

Refering to the mid function followed. It is a solution written in Haskell.

result :: (Floating a) => a<br /> result = let x = sqrt 16.0<br /> in x+1.0</p> <p>fact 0 = 1<br /> fact n = n * fact (n-1) </p> <p>f l = reverse (f' l [])<br /> where f' [] r = r<br /> f' (x:xs) r = (2*x) : (f' xs r) </p> <p>avg lst = (sum lst ) `div` (length lst)</p> <p>mid' lst1 lst2 = if (null lst2) || (null (tail lst2))<br /> then head lst1<br /> else mid' (tail lst1) (tail (tail lst2))<br /> mid lst = mid' lst lst</p> <p>neg [] = 0<br /> neg (a:as) | a<0 = 1+(neg as)<br /> | otherwise = neg as</p> <p>main=do<br /> print result<br /> print $ fact 5<br /> print $ f [1,2,3,4]<br /> print $ avg [1,2,1,4]<br /> print $ mid [1,2,3,4,5,6]<br /> print $ neg [1,-1,-2,-3,2]

--Program Output<br /> $ runghc Main.hs<br /> 5.0<br /> 120<br /> [8,6,4,2]<br /> 2<br /> 4<br /> 3