面试题16：反转链表（剑指offer）

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

public ListNode ReverseList(ListNode head)
{
    ListNode pReverseHead = null;
    var pNode = head;
    ListNode pPrev = null;
    while (pNode!=null)
    {
        var pNext = pNode.next;
        if (pNext == null)
            pReverseHead = pNode;
        pNode.next = pPrev;
        pPrev = pNode;
        pNode = pNext;
    }
    return pReverseHead;
}
public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int x)
    {
        val = x;
    }
}

微信图片_20210228150623.jpg

在图所示的链表中，h、i和j是3个相邻的结点。假设经过若干操作，我们已经把结点h之前的指针调整完毕，这些结点的m_pNext都指向前面一个结点。接下来我们把i的m_pNext指向h，此时的链表结构如图（b）所示。

不难注意到，由于结点i 的 m_pNext 指向了它的前一个结点，导致我们无法在链表中遍历到结点j。为了避免链表在结点i处断开，我们需要在调整结点i的m_pNext之前，把结点j保存下来。