题目

输入一个链表，反转链表后，输出新链表的表头。

思路

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

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

即在调整结点i的m_pNext指针时，除了需要知道结点i本身之外，还需要i的前一个结点h，因为我们需要把结点i的m_pNext指向结点h。同时，还需要实现保存i的一个结点j，以防止链表断开。故我们需要定义3个指针，分别指向当前遍历到的结点、它的前一个结点及后一个结点。故反转结束后，新链表的头的结点就是原来链表的尾部结点。尾部结点为m_pNext为null的结点。

  • 考虑程序的鲁棒性，1.当链表头指针为空 2.输入链表只有一个节点 3.输入链表有多个节点
  • 选择三个节点，分别是当前节点ahead，当前节点的前一个节点before、后一个节点next
  • 首先确定当前节点的下一个节点是next=ahead.next
  • 然后判断下一个节点是否为空，如果为空意味着到达链表的末尾，此时链表已经反转
  • 然后转换第一个节点的位置 ahead.next=before
  • 将前一个节点和当前节点向向下移动一个位置，即为：before = ahead ahead= next（ahead.next）
  • 最后返回反转后的节点

代码


public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode resulthead = null;
        ListNode ahead = head;
        ListNode before= null;
        if(ahead==null || ahead.next==null){
            return ahead;
        }
            
        while(ahead!=null){
            ListNode next = ahead.next;
           if(next==null)
               resulthead=ahead;
            ahead.next = before;
            before = ahead;
            ahead = next;
            
        }
        return resulthead;
    }
}