反转链表

定义问题:

定义一个函数,输入链表的头结点,反转该链表并输出发转后链表的头结点 (这里必须是在原链表上进行发转,而不是新做一个链表)

结点定义如下:

struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};

原链表:

+-----+    +-----+    +-----+    +-----+
|     |    |     |    |     |    |     |
|  A  +---->  B  +--->+  C  +--->+  D  |
|     |    |     |    |     |    |     |
+-----+    +-----+    +-----+    +-----+

由于是在原链表上进行反转的,所以可以得出下图:

中间态:

+-----+    +-----+    +-----+    +-----+
|     |    |     |    |     |    |     |
|  A  +<---+  B  |    |  C  +--->+  D  |
|     |    |     |    |     |    |     |
+-----+    +--+--+    +--+--+    +--+--+
              ^          ^          ^
              |          |          |
              +          +          +
            pPrev      pNode      pNext

反转操作顺序:

1. 断开pNode向next的指向
   1.1 保存pNode向next的指向到pNext变量
2. pNode的next指向pPrev
3. pPrev前移一位,到pNode
4. pNode前移一位到pNext

代码如下:

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;
}

由于是在原链表上进行的反序,所以上述的赋值顺序及其重要, 可以看到一个规律就是: 一个值一旦将其给出去,那它就立刻接受一个新值,而且是一个环, 这也是一个debug的点

这里需要注意最终的每个变量都被赋值,并且被赋予到其他变量, 例如:

pNode->m_pNext = pPrev;
pPrev = pNode;

ref:

1. 剑指Offer, 面试题16