206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution1:

pNext用于移动pNode, pPrev和找到新的链表头, 保存pPrev用于创建新的链接.

三个变量: 新的链表头reverseHead, 游标结点pNode, 前序结点pPrev,
四个操作: 循环内部创建下一结点, 改变游标指向前序结点, 前序结点移动到游标结点, 游标结点移动到下一结点.
两个判断: 游标结点非空指针时, 进行循环操作; 游标的下一结点为空指针时, 记录新的链表头

// basic reverse
// Time:O(n), Space:O(1)
class Solution {
 public:
  ListNode* reverseList(ListNode* head) {
    ListNode* reverseHead = nullptr;
    ListNode* pNode = head;
    ListNode* pPrev = nullptr;
    while (pNode != nullptr) {
      ListNode* pNext = pNode->next;
      if (pNext == nullptr) {
        reverseHead = pNode;
      }
      pNode->next = pPrev;
      pPrev = pNode;
      pNode = pNext;
    }
    return reverseHead;
  }

};

Solution2:

1->2->3->4->5;

当5作为头结点指向4的时, 4仍旧指向5, 可以通过每次保留上一次处理的结点, 从末尾前指向

几个注意点:

1, 主要在中间过程中, 找出反转后的头结点;
2, 在反转结束后, 尾指针指向nullptr;
3, 要注意空链表的情况;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

// Time:O(n^2), Space:O(1)
class Solution {
 public:
  ListNode* reverseList(ListNode* head) {
    if (head == nullptr) return head;
    ListNode *pNode = nullptr, *reverseHead = nullptr;
    while (pNode != head) {
      ListNode *p = head;
      while (p->next != pNode) {
        p = p->next;
      }

      if (pNode != nullptr) {
        pNode->next = p;
      } else {
        reverseHead = p;
      }
      pNode = p;
    }
    pNode->next = nullptr;
    return reverseHead;
  }
};

Solution: Follow up1

从随意位置反转链表, 在该位置后的结点不变。
需要保存一个新的头结点, reverseHead; 以及另一结点, nextNode用于, 反转之后的结点拼接。

// follow up1: iteratively
class Solution {
 public:
  ListNode* reverseList(ListNode* head, int k) {
    if (head == nullptr) return head;
    ListNode *pNode = head;
    for (int i = 0; i < k-1; i++) {
      if (pNode->next == nullptr) return head;
      pNode = pNode->next;
    }
    ListNode *reverseHead = pNode, *nextNode = pNode->next;
    while (pNode != head) {
      ListNode *p = head;
      while (p->next != pNode) {
        p = p->next;
      }
      pNode->next = p;
      pNode = p;
    }
    pNode->next = nextNode;
    return reverseHead;
  }
};

一个测试Sample

input:
[1, 2, 3, 4, 5]
int k = 2;

output:
[2, 1, 3, 4, 5]

Solution: Follow up2

反转呈现周期性, 但是若不满这个周期, 不会反转链表.

// follow up2: recursively
class Solution {
 public:
  ListNode* reverseList(ListNode* head, int k) {
    if (head == nullptr || k <= 1) return head;

    ListNode *pNode = head, *reverseHead = nullptr,
        *lastHead = head, *lastTail = nullptr;
    for (;;) {
      for (int i = 0; i < k-1; i++) {
        if (pNode->next == nullptr) return reverseHead;
        pNode = pNode->next;
      }
      ListNode *segHead = pNode, *nextNode = pNode->next;
      if (reverseHead == nullptr) {
        reverseHead = segHead;
      }
      if (lastTail != nullptr) {
        lastTail->next = segHead;
      }

      while (pNode != lastHead) {
        ListNode *p = lastHead;
        while (p->next != pNode) {
          p = p->next;
        }
        pNode->next = p;
        pNode = p;
      }
      pNode->next = nextNode;
      lastTail = lastHead;
      lastHead = nextNode;
      pNode = nextNode;
      if (lastHead == nullptr) {
        return reverseHead;
      }
    }
    return reverseHead;
  }
};

测试Sample:

/*
input:
[1,2,3,4,5,6,7,8]
3

[3, 2, 1, 6, 5, 4, 7, 8]


input:
[1,2,3,4,5,6,7,8]
2

[2, 1, 4, 3, 6, 5, 8, 7]
*/