LeetCode | 206. 反转链表

OJ链接

• 这里有两个思路

---

我们先来看第一个思路：

• 创建一个新的链表，然后将原链表头插
• 头插需要保存下一个的地址，再头插

代码如下：

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* newHead = NULL;while(cur){struct ListNode*next = cur->next;//头插cur->next = newHead;newHead = cur;cur = next;}return newHead;
}

---

思路二：

• 这个思路二，就是定义三个指针，n1,n2,n3
• 让n1掷为空，n2指向头结点，n3指向n2->next，也就是第二个节点
• 然后我们就开始走，n1给了n2，n2给了n3，n3继续往前走
• 当n2走到空才停下
• 最后返回n1，就相当于逆转的链表

代码如下：

struct ListNode* reverseList(struct ListNode* head) {if(head == NULL)return NULL;struct ListNode* n1 = NULL;struct ListNode* n2 = head;struct ListNode* n3 = n2->next;while(n2 != NULL){n2->next = n1;n1 = n2;n2 = n3;if(n3)n3 = n3->next;}return n1;
}