翻转单链表

简介: 翻转单链表

反转单链表

牛客网看到了这样一道翻转单链表的题,思考了许久,通过画图后,想到了迭代和创建新链表两种方法。

接口函数

/**
 * 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; //返回新的头
}

方法二示意图:


相关文章
|
8月前
|
Java C++ Python
leetcode-226:翻转二叉树
leetcode-226:翻转二叉树
32 0
Leetcode226.翻转二叉树
Leetcode226.翻转二叉树
42 0
LeetCode | 226. 翻转二叉树
LeetCode | 226. 翻转二叉树
|
8月前
|
C++
翻转二叉树(C++)
翻转二叉树(C++)
35 0
|
8月前
leetcode-61:旋转链表
leetcode-61:旋转链表
37 0
|
8月前
「LeetCode」61. 旋转链表
「LeetCode」61. 旋转链表
49 0
|
Java Python
leetcode:61.旋转链表
给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
76 0
leetcode 226 翻转二叉树
leetcode 226 翻转二叉树
55 0
leetcode 226 翻转二叉树