l********n
发帖数: 1038 | 1 现有两种方法，一种递归，一种直接存指针反转。哪种好？
Java版
static List Reverse(List L)
{
//firstly check if L is empty or only has one element then return
if(L==null || L.next==null)
return L;
//otherwise, we can use our recursive method
List remainingReverse = Reverse(L.next);
//next we have two step steps, firstly we need update the tail of
remaining reverse as our head L
L.next.next = L;//this (L.next) is the key to get te tail in constant
time!
//Very important, we need set L.next to NULL after that! Otherwise it's
causing cycles in list
L.next = null;
//finally we return the reverse List
return remainingReverse;
}
C++版
ListNode* ReverseList(ListNode* pHead)
{
ListNode* pReversedHead = NULL;
ListNode* pNode = pHead;
ListNode* pPrev = NULL;
while(pNode != NULL)
{
ListNode* pNext = pNode->m_pNext;
if(pNext == NULL)
pReversedHead = pNode;
pNode->m_pNext = pPrev;
pPrev = pNode;
pNode = pNext;
}
return pReversedHead;
} | z*********8
发帖数: 2070 | | l********n
发帖数: 1038 | 3 这两种都是one-pass，算不算都是in-place？第一种用了堆栈,第二种用了辅助空间 | z*********8
发帖数: 2070 | 4 算
【在 l********n 的大作中提到】
: 这两种都是one-pass，算不算都是in-place？第一种用了堆栈,第二种用了辅助空间
| l********n
发帖数: 1038 | |
|
