数据结构与算法---线性表---反转链表

LeetCode 206反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

---

学习之前，巩固一下链表知识：

更多学习请参考数据结构学习(一)

---

链表结构以及链表逆序后的效果：

递归方法：

假设：我们已经将reverseList(head)方法实现了，那么我们可以用此方法实现reverseList(head->next)

reverseList(head->next)的效果如下图所示：

此时，只需要将 4处的节点指向5的节点， 5处的节点指向null 那么，reverseList(head)的反转就完成了。

再考虑边界值： head == NULL，空的链表，直接返回head或者null head->next == NULL，只有一个节点，翻转后也是它自己，所以直接返回head

可以得到以下代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ //递归方法 if(head == NULL) return head; /**head->next == NULL代表链表只有一个节点，也就是5的next为NULL*/ if(head->next == NULL) return head; struct ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = NULL; return newHead; }

---

非递归(迭代)方法

首先，判断边界条件需要添加 然后，创建一个新的结点newHead，用于接收新的链表

然后重复以下步骤：

然鹅，第一步中，5节点指向null，那么4就丢失了，因此，为了4不丢失，需要定义一个临时变量tempNode等于4节点。

循环结束条件：head != NULL 那么，不难写成代码：

struct ListNode* reverseList(struct ListNode* head){ //非递归方法 if(head == NULL || head->next == NULL) return head; struct ListNode *newHead = NULL; while(head != NULL) { struct ListNode *tempNode = head->next; //head->next = (*head).next = 5节点.next = 存储着4节点的地址值 head->next = newHead; newHead = head; head = tempNode; //右边左 } return newHead; }

以上是MJ老师的写法

---

以下为于海老师写的代码

于海老师写的比这个多一步，会将head赋值给p，对p操作，这样，head指针是不变的。 结果是，我们反转链表，不会对原有链表进行修改。 代码如下：

//非递归方法 struct Node* reverseList(struct Node *head) { if(head == NULL || head->next == NULL) return head; // 定义遍历指针，初始化为头结点 struct Node *p = head; // 反转后的链表头部 struct Node *newH = NULL; // 遍历链表 while (p != NULL) { // 记录下一个结点 struct Node *temp = p->next; // 当前结点的next指向新链表头部 p->next = newH; // 更改新链表头部为当前结点 newH = p; // 移动p指针 p = temp; } // 返回反转后的链表头结点 return newH; }