题解 | #反转链表#

加入一个首元结点，头插法

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == nullptr || pHead->next == nullptr) { 
          // 空和单元素不用翻转直接返回
            return pHead;
        }
        
        auto new_head = std::make_unique<ListNode>(-1);
        ListNode *old_head;
        
        while (pHead != nullptr) {
            old_head = pHead;
            pHead = pHead->next;
            old_head->next = new_head->next;
            new_head->next = old_head;
        }
        
        return new_head->next;
    }
};

不加首元结点

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
      if (pHead == nullptr || pHead->next == nullptr) {
        return pHead;
      }
      
      ListNode *cur, *pre, *nex;
      
      pre = nullptr;
      cur = pHead;
      nex = pHead->next;
      
      while (nex) {
        cur->next = pre;
        pre = cur;
        cur = nex;
        nex = nex->next;
      }
      
      cur->next = pre;
      
      return cur;
    }
};