即给定一个链表,以及两个位置m,n,将从第m个节点到第n个节点的链表进行反转。要求最好是只扫描一次链表,以及in-place去做。比如,对于1->2->3->4->5->NULL, m = 2 and n = 4
,反转后返回1->4->3->2->5->NULL
。
开始想到的方法是,使用一个栈,从m到n,将节点的值入栈,然后再扫一遍链表,从m到n,再将值依次出栈,更改节点元素值即可。如此,有两个不好的地方,首先,多开辟了存储空间,最坏情况下,需要浪费O(n)的存储空间;再者,需要遍历两次。
Read More