反转链表

• 输入一个链表，反转链表后，输出新链表的表头。
• Java 代码（递归形式）：
  • 首先在递归的每层记录当前节点的后继，并将其赋值给后继的next
  • 其次要记录最后一个节点，不做修改并层层返回

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode next = head.next;
        ListNode newHead = reverseList(head.next);
        next.next = head;
        head.next = null;
        return newHead;
    }
}

• C++ 代码
  • 增加一个头结点会更简单
  • 或者先提取出一个head，分成了两个链表，之后把除了head那个链表逐项加载head这个链表的头部。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(!pHead) return nullptr;
        if(!pHead->next) return pHead;
        ListNode* p ,*q;
        p=pHead->next;
        q=p->next;
        pHead->next=NULL;
        while(p)
        {
            p->next=pHead;
            pHead=p;
            p=q;
            if(!p) break;
            q=p->next;
        }
        return pHead；      
    }
};