反转单链表
在牛客网看到了这样一道翻转单链表的题，思考了许久，通过画图后，想到了迭代和创建新链表两种方法。
接口函数
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pHead ListNode类 * @return ListNode类 */ //方法一：迭代法 struct ListNode* ReverseList(struct ListNode* pHead) { if (!pHead) //如果链表为空，则不需要进行翻转，直接返回原结点 return pHead; struct ListNode* n1, * n2, * n3; //定义三个指针，n1，n2用来进行翻转，n3用来记录下一个位置 n1 = NULL; n2 = pHead; n3 = pHead->next; while (1) { n2->next = n1; //将后面结点的指针域指向前面的结点，实现翻转 n1 = n2; //指针下滑 n2 = n3; //指针下滑 if (!n2) //当n2为空的时候，结束循环，此时n1为新链表的头结点 break; n3 = n3->next; //指针下滑 } return n1; }
方法一示意图：
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pHead ListNode类 * @return ListNode类 */ //方法二：创建新链表，将旧链表的结点从前往后头插到新链表，实现旧链表的翻转 struct ListNode* ReverseList(struct ListNode* pHead) { struct ListNode* newHead = NULL; //创建新链表的头结点 struct ListNode* cur = pHead, *end = pHead->next; //定义两个指针用来记录当前位置和保存下一个位置 while (cur) //若当前位置为空，则直接退出循环 { cur->next = newHead; //使当前位置的指针域指向新的头 newHead = cur; //更改头结点位置 cur = end; //记录当前位置的指针下滑 if (!cur) //如果cur下滑后为空，则立即退出循环，防止end变为野指针 break; end = end->next; //end下滑 } return newHead; //返回新的头 }
方法二示意图：
