精华内容
参与话题
问答
  • 单链表反转

    万次阅读 多人点赞 2013-04-25 16:20:26
     方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。  方法2:使用三个指针遍历单链表,逐个链接点进行反转。  方法3:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head节点)之后,最后将第...

            单链表的翻转是一道很基本的算法题。

            方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。

            方法2:使用三个指针遍历单链表,逐个链接点进行反转。

            方法3:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head节点)之后,最后将第一个节点挪到新表的表尾。

            方法1的问题是浪费空间。方法2和方法3效率相当。一般方法2较为常用。

    方法2代码:

    Node * ReverseList(Node *head)
    {
    	Node *p1,*p2,*p3;
    	if(head==NULL||*head==NULL)
    	return head;
    	p1=head;
    	p2=p1->next;
    	while(p2)             //注意条件
    	{
    		p3=p2->next;	      //要改变p2->next的指针,所以必须先保留p2->next	     
    		p2->next=p1;
    		p1=p2;		      //循环往后
    		p2=p3;
    	}
    	head->next=NULL;   //原先的head已经变成tail,别忘了置空,只有到这步才能置空
    	*head=p1;
    	return head;
    }
    


    方法3代码:

    Node* ReverseList(Node* head) 
    { 
        Node *p,*q;  
        p=head->next; 
        while(p->next!=NULL)      //在这个循环过程中p所指的元素一直是不变的
    	{
            q=p->next; 
            p->next=q->next; 
            q->next=head->next; 
            head->next=q; 
    	} 
        p->next=head;            //相当于成环 
        head=p->next->next;       //新head变为原head的next 
        p->next->next=NULL;     //断掉环 
        return head;   
    }
    


     

           附加一道题目,《编程之美》的3.4:从无头链表中删除节点。假设有一个没有头指针的单链表。一个指针指向此链表中间的一个节点(不是第一个,也不是最后一个节点),请将该节点从单链表中删除。

           分析:无法知道前续的节点,只能知晓后续节点,所以存在一个难点,如何将前后两段连接起来。由于链表是要删除操作,所以多处一个可用空间。所以可以用翻转操作方法1的思想来解决。将需要删除节点的节点复制为其后续节点就可以了,这样后续节点已经不再链表中,可以进行析构。

     

    展开全文
  • 【图文解析】反转一个单链表

    万次阅读 多人点赞 2019-03-18 15:26:38
    反转一个链表 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 结构体定义 struct ...


    例题描述

    反转一个链表

    示例:

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

    结构体定义

    struct ListNode {
    	int val;
    	struct ListNode *next;
    };
    

    在这里插入图片描述


    思路一

    先对原链表做头删操作,再对新链表做头插

    1. 定义一个新head头指针,标记为newHead,将它初始为NULL,并非指向NULL,最后我们选择返回这个newHead指针作为新链表的头指针。
      在这里插入图片描述
    2. 定义一个结点node作为"临时中转站",初始化与否并无大影响。
    3. 进行循环遍历链表各个结点,判定head指针是否为空,即是否到达了原链表的结尾。如果不为空,说明还没有到达尾部。如果程序第一次运行就没有进入循环,说明传入了一个空链表,此时返回newHead新链表的头指针,同样返回NULL,这样处理也是合理的。
    4. 以下开始逆序链表逻辑:在当前指针不为NULL时,先对原链表做头删操作,再对新链表做头插操作。即使用循环进行操作:
    5. node指针指向传入函数链表的头指针head,两指针指向保持相同。
      在这里插入图片描述
    6. 然后让head指针指向它的next结点,此时旧链表已经完成了头删操作。第一个结点已经被"切割"下来。接下来要做的就是对新链表进行头插操作,使结点放入新链表。
      在这里插入图片描述
    7. node指针的next下一个结点指向新链表的头指针newHead,完成结点的链接,即头插入新的链表中。然后更新newHead指向为新链表的头结点。进行下一次循环。
      在这里插入图片描述8. 最终head指针指向了原链表的结尾,即为NULL,退出循环,此时新链表已经反转完毕,情况如图:
      在这里插入图片描述
    8. 最终返回新链表头指针newHead即可。

    代码实现

    struct ListNode *reverseList(struct ListNode* head) {
    	struct ListNode *newHead = NULL;
    	struct ListNode *node;
    	while (head != NULL) {
    		//1. 对之前的链表做头删
    		node = head;
    		head = head->next;
    		
    		//2. 对新链表做头插
    		node->next = newHead;
    		newHead = node;
    	}
    	return newHead;
    }
    

    思路二

    1. 利用选择语句,找到空链表的情况,此情况返回NULL空指针,因为空链表不能反转,或者说反转之后还是一个空链表,返回空。
    2. 利用三个指针p0"前指针"、p1“当前指针”、p2"后指针"来分批处理链表元素,p0置为NULL,它将作为链表的尾结点向前推进处理,p1指向旧链表的头指针headp2指向旧链表的头指针的next结点。
      在这里插入图片描述
    3. 开始遍历链表,循环判定因子为p1,当它为空时到达链表尾部跳出循环。否则在表中执行循环内逻辑:将p1指向的当前结点的下一个结点指向p0,即前一个结点。
      此时p0NULL,那么p1的下一个结点就为空了,它现在是最后一个结点。
      在这里插入图片描述
    4. 然后将p0指针指向p1,将p1指针指向p2,注意这两步不可以调换顺序,否则正确向后挪移一位。此时完成了三个指针的一轮更迭。
    5. 判定p2指针是否为空,如果为空说明此时p2到达了链表结尾,当前指针p1的指向为最后一个结点,它的next即为空。如果不为空,将p2更新到下一个结点,进行下一次循环。
      在这里插入图片描述
    6. 下一次进行循环时,就会把截断结点链接到新链表的头部,同时更新三个指针。继续循环。
      在这里插入图片描述
    7. 循环终止条件为:p1指向了链表尾部的NULL,此时p1的前指针p0即指向了反转后的链表,它就是新链表的head头指针。此时返回p0即可。

    代码实现

    struct ListNode *reverseList(struct ListNode* head) {
    	if (head == NULL) {
    		return NULL;
    	}
    	struct ListNode *p0 = NULL;
    	struct ListNode *p1 = head;
    	struct ListNode *p2 = head->next;
    	while (p1 != NULL) {
    		p1->next = p0;
    
    		p0 = p1;
    		p1 = p2;
    		if (p2 != NULL) {
    			p2 = p2->next;
    		}
    	}
    	return p0;
    }
    
    展开全文
  • 单链表反转两种方法

    万次阅读 多人点赞 2019-01-29 20:31:07
    最近同学介绍了一个lettcode(力扣)OJ给我,个人认为这个网站比母校的oj,杭电oj界面友好很多,题库充足,且支持多种主流语言,很适合闲时刷刷提高算法能力,算法的练习如同内功的修炼,碰到算法问题,经常有一种无力...

    最近同学介绍了一个lettcode(力扣)OJ给我,个人认为这个网站比母校的oj,杭电oj界面友好很多,题库充足,且支持多种主流语言,很适合闲时刷刷提高算法能力,算法的练习如同内功的修炼,碰到算法问题,经常有一种无力感,只能慢慢总结了。

    链表是一种重要的数据结构,因为有递归性质,所以总是难以理解,涉及链表的复杂操作总是感觉一头雾水,看别人的实现代码总是似懂非懂,看完就忘,实际上就是没有理解透彻,特意花了一天时间重新学习了单链表的常见操作-单链表反转,理解和总结两种实现方法。

    首先要了解一个链表节点的数据结构:
    在这里插入图片描述
    value代表该节点存储的值,next指向下一个节点,next可能指向一个单一节点,也可能指向一个链表,也可能指向null(代表尾节点)。
    方法一:头节点插入法
    实现步骤:

    1. 创建一个带头节点的链表resultList
    2. 定义一个循环链表变量p,p的初始值为待反转的链表
    3. 遍历待反转的链表,遍历条件为 (p !=null)
      3.1 定义一个临时链表变量tempList保存p->next的值(因为p->next值会改变),用于下一次循环。
      3.2 把p当前指向的首节点和resultList链表的头节点之后的节点拼接起来。
      3.3 把3.2步骤中拼接的节点 再拼接到resultList头节点后。
      3.4 p重新赋值为3.1步骤中保存的tempList的值。
    4. 返回resultList->next.即反转后的链表。

    图解:
    在这里插入图片描述
    图1就是待反转的原始链表,图2是 带头节点的链表resultList。
    可以看到p是一个循环变量,初始值指向待反转的原始链表。
    通过p变量遍历链表,在遍历中(列举的值为第一次循环的情况):

    • 定义一个临时链表变量tempList保存p->next的值,tempList指向图1.2
    • 把p当前指向的首节点(图1.1)和resultList链表的头节点之后的节点(图2.2)拼接起来。
    • 把3.2步骤中拼接的节点(图3.2) 再拼接到resultList头节点后。
    • p重新赋值为3.1步骤中保存的tempList的值,即图1.2。

    最后返回resultList->next,也就是去除了头节点-1的值。

    通过头结点插入法实现链表反转功能,主要难点就是在循环中的3.2和3.3步骤的理解。
    需要注意的是,就是关注循环变量p的值,也就是指向的变化,传统的遍历过程就是条件为p!=null,处理,p=p->next。但是在这个头结点插入代码中,p->next的值发生的变化,因为要将resultList结果链表的内容拼接到p的首节点后,所以要定义一个临时变量存p->next。

    方法二:就地反转
    头结点插入法的实质是重新创建了一个新的链表,通过遍历待反转链表,将链表每一个节点插入到创建的链表中,然后的到的这个创建的链表就是反转后的链表。而就地反转实质就是在待反转链表基础上修改节点顺序得到反转链表。所以原理还是不同的。

    图解:
    在这里插入图片描述
    个人认为就地反转比头结点插入稍微难理解一点。
    宏观上来看,要实现节点1和节点2反转,需要将节点1插入节点2和节点3当中,然后将头节点为2的链表插入结果链表头结点后面,然后再后移一个节点做同样的操作。
    然而涉及到两个节点的循环赋值,这个操作顺序就比较重要了。
    正确的步骤是先将节点2切分出来,再将节点2插入-1和1之间。

    实现步骤

    1. 创建一个带头节点的链表resultList,头结点指向待反转的链表。
    2. 创建p、pNext两个用于循环操作,分别指向两个待反转节点的位置,初始值如图所示,指向1和2
    3. 遍历带反转的链表,循环条件是pNext!=null.
      3.1 从链表中分割出pNext节点,也就是让p指向pNext->next。
      3.2 让pNext指向经过3.1操作之后的resultList.next(1->3->4->5)
      3.3 让resultList头结点指向pNext(2->1->3->4->5)
      3.4 让pNext指向p的下一个节点
      难点在于理解循环中resultList.next指向性的变化,以及p和pNext两个变量的变化,p指向的链表首结点永远是1,只是节点1在resultList链表中位置在发生变化,而pNext是随着p移动的,脑子中间可以有一个摆绳模型,在起始点位置发力,绳子的高点位置会移到绳尾,那个最高点就是p变量位置。

    代码实现:
    头结点插入:

        public static ListNode reverseListByInsert(ListNode listNode){
            //定义一个带头节点的
            ListNode resultList = new ListNode(-1);
            //循环节点
            ListNode p = listNode;
            while(p!= null){
                //保存插入点之后的数据
                ListNode tempList = p.next;
                p.next = resultList.next;
                resultList.next = p;
                p = tempList;
            }
            return resultList.next;
        }
    

    就地反转:

    public static ListNode reverseListByLocal(ListNode listNode){
            ListNode resultList = new ListNode(-1);
            resultList.next= listNode;
            ListNode p = listNode;
            ListNode pNext = p.next;
            while (pNext!=null){
                p.next = pNext.next;
                pNext.next = resultList.next;
                resultList.next = pNext;
                pNext=p.next;
            }
            return resultList.next;
        }
    

    单链表的操作困扰了很多年,或许还将困扰下去,但是至少有了更加深入的认识。这部分内容确实相对有点难以理解。推荐的学习方法就是先看别人代码,再画图了解代码的每一个过程,再根据画的图独立写代码实现,然后再调试debug,查看变量变化情况,再找类似练习题,多想多练。(就地反转的方法还需要细讲)。

    展开全文
  • 【算法】单链表反转

    千次阅读 2018-07-10 17:43:34
    我个人觉得你要想进大厂,进技术氛围牛逼的团队,算法是必考察的,Android中Handler机制中的Message缓存池设计就是普通的单链表操作,HashMap中的解决Hash碰撞也是用链表数据结构来实现,常用的集合类里面的实现逻辑...

    前言:

    算法重不重要:这个话题有史以来,公说公有理婆说婆有理。我个人觉得你要想进大厂,进技术氛围牛逼的团队,算法是必考察的,Android中Handler机制中的Message缓存池设计就是普通的单链表操作,HashMap中的解决Hash碰撞也是用链表数据结构来实现,常用的集合类里面的实现逻辑基本都是各种数据结构,Android各种框架用到的缓存机制比如Lru算法,还有各种XX池的设计背后都是数据结构跟算法。

    1、单链表的结点结构:

    这里写图片描述

    • data域:存储数据元素信息的域称为数据域;
    • next域:存储直接后继位置的域称为指针域(链域),存储直接的下一个节点地址。
    • data域 + next域:组成数据的存储映射,称为结点;
      注意:
      : ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
      : ②每个结点只有一个链域的链表称为单链表(Single Linked List)。
    class Node {
    	    private int Data;// 数据域
    	    private Node Next;// 指针域【链域】,存储下一个节点
    	    public Node(int Data) {
    	        this.Data = Data;
    	    }
    	
    	    public int getData() {
    	        return Data;
    	    }
    	
    	    public void setData(int Data) {
    	        this.Data = Data;
    	    }
    	
    	    public Node getNext() {
    	        return Next;
    	    }
    	
    	    public void setNext(Node Next) {
    	        this.Next = Next;
    	    }
    	}
    

    2、解题思路:

    2.1、问题描述:

    将单链表数据:0,1,2,3 转为:3,2,1,0

    2.2、递归反转法:

    • 在反转当前节点之前先反转后续节点。这样从头结点开始,层层深入直到尾结点才开始反转指针域的指向。

    • 就是从尾结点开始,逆向反转各个结点的指针域指向。

        head:是前一结点的指针域。
        head.getNext():是当前结点的指针域。
        reHead:是反转后新链表的头结点(即原来单链表的尾结点)
      

    2.3、遍历反转法:

    • 从前往后反转各个结点的指针域的指向。

    • 将当前节点cur的下一个节点 cur.getNext()缓存到temp后,然后更改当前节点指针指向上一结点pre。

    • 也就是说在反转当前结点指针指向前,先把当前结点的指针域用tmp临时保存,以便下一次使用,其过程可表示如下:

           pre:上一结点
           cur: 当前结点
           tmp: 临时结点,用于保存下一结点
      

    2.4、具体代码实现:

    public class LinkedListReverse01 {
    	    public static void main(String[] args) {
    	        Node head = new Node(0);
    	        Node node1 = new Node(1);
    	        Node node2 = new Node(2);
    	        Node node3 = new Node(3);
    	        head.setNext(node1);
    	        node1.setNext(node2);
    	        node2.setNext(node3);
    	
    	        // 打印反转前的链表
    	        Node h = head;
    	        while (null != h) {
    	            System.out.print(h.getData() + " ");
    	            h = h.getNext();
    	        }
    	       
    	//        head = Reverse1(head);
    	        head = Reverse2(head);
    	
    	        System.out.println("\n**************************");
    	        // 打印反转后的结果
    	        while (null != head) {
    	            System.out.print(head.getData() + " ");
    	            head = head.getNext();
    	        }
    	    }
    	
    	    /**
    	     * 递归反转法,从尾结点开始,逆向反转各个结点的指针域指向。
    	     */
    	    public static Node Reverse1(Node head) {
    	        // head看作是前一结点,head.getNext()是当前结点,reHead是反转后新链表的头结点
    	        if (head == null || head.getNext() == null) {
    	            return head;// 若为空链或者当前结点在尾结点,则直接还回
    	        }
    	        Node reHead = Reverse1(head.getNext());// 先反转后续节点head.getNext()
    	        head.getNext().setNext(head);// 将当前结点的指针域指向前一结点
    	        head.setNext(null);// 前一结点的指针域令为null;
    	        return reHead;// 反转后新链表的头结点
    	    }
    	
    	    /**
    	     * 遍历反转法:从前往后反转各个结点的指针域的指向。
    	     *
    	     * @param head
    	     * @return
    	     */
    	    public static Node Reverse2(Node head) {
    	        if (head == null) return head;
    	        Node pre = head;// 上一结点
    	        Node cur = head.getNext();// 当前结点
    	        Node tmp;// 临时结点,用于保存当前结点的指针域(即下一结点)
    	        while (cur != null) {// 当前结点为null,说明位于尾结点
    	            tmp = cur.getNext();
    	            cur.setNext(pre);// 反转指针域的指向
    	            pre = cur; // 指针往下移动
    	            cur = tmp;
    	        }
    	        // 最后将原链表的头节点的指针域置为null,还回新链表的头结点,即原链表的尾结点
    	        head.setNext(null);
    	        return pre;
    	    }
    	}
    
    展开全文
  • 看图理解单链表反转

    千次阅读 2018-07-04 11:45:48
    如何把一个单链表进行反转?方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。方法2:使用三个指针遍历单链表,逐个链接点进行反转。方法3:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head...
  • 单链表反转

    2020-11-25 15:13:57
    单链表节点 public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } 方案一 迭代 /** * 迭代法 * 先保存当前结点的下一个节点 * 将当前结点指向我们定义的上一个结点 * 然后把...
  • 单链表反转_python版

    千次阅读 多人点赞 2019-03-21 13:01:10
    代码如下: class Node(object): def __init__(self, elem, next_=None): self.elem = elem self.next = next_ def reverseList(head): if head == None or head.next==None: # 若链表为空或者仅一个数就直...
  • 反转一个单链表

    2019-07-09 16:20:56
    #include <stdio.h> #include <...typedef struct slistnode//单链表节点 { sdatatype _data; struct slistnode *pnext; }node,*pnode; typedef struct slist//给一个头指针保存第一个...
  • 希望各位从此不再纠结单链表反转 单链表,链表,表 不多废话,看看如何反转一个单链表,我将清晰的展示两种方法 我将把每一步分解出来图示,并于每一步说明执行了那些操作,然后在最后附上代码,以及力扣上的练习 第...
  • 单链表实现反转的三种方法

    千次阅读 2017-07-17 20:03:31
    单链表的操作是面试中经常会遇到的问题,今天总结一下反转的几种方案: 1 ,两两对换 2, 放入数组,倒置数组 3, 递归实现
  • 单向链表反转(倒置)问题

    万次阅读 多人点赞 2017-03-14 19:40:02
    今天遇到单向链表的反转的问题,于是静下心来好好想了一番。 解题思路如下图:假设当前创建好的链表如下:首先让头节点与第一个元素节点断开,但是要注意在断开之前需要用p指针指向第一个元素节点来保存第一个元素...
  • 单链表反转C语言实现

    万次阅读 2014-07-05 09:51:03
    1.循环反转单链表 循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可。   代码: # include # include using namespace std; struct linkNode { int val; linkNode *next; ...
  • C语言实现单链表反转

    千次阅读 2018-09-20 17:09:31
    最近在考研复习,记录一下基础的数据结构算法,有事没事翻一翻,以防忘了 自己写了个翻转链表算法,感觉要比别人的要通俗易懂些 void Reverse(List *L){ //分别是当前节点,直接前驱节点,直接后继节点 ...
  • 就一开始相当于我们先创建个pre的结点,其地址是NULL,这个就作为我们反转之后链表的末尾了,然后从头结点之后的第一个结点开始,pre向右边移, 每一个都往pre指。 最后输出的时候我为了方便,给反转之后的链表加了...
  • 单链表反转C语言

    2019-12-16 23:02:34
    单链表反转C语言) 方法一:三指针法 思路: a,b,c三个指针分别指向三个位置 a指针和b指针用来反转两个结点 c指针指向下一个节点用来标记和向前推进 代码 //单链表反转函数 //三指针法 /* a,b,c三个指针...
  • Java单链表反转 详细过程

    万次阅读 多人点赞 2016-04-11 10:36:57
    Java单链表反转 Java实现单链表翻转 使用递归法实现单链表反转,使用遍历反转法:递归反转法是从后往前逆序反转指针域的指向,而遍历反转法是从前往后反转各个结点的指针域的指向。  【尊重原创,转载请注明出处】...
  • C语言实现单链表反转(图文) 据说是一道微软的面试题改编 挺有名的,据说很多人面试时 被要求当场纸写程序基本上都没答出来或者没答完整 本着他人故事不要成为我的事故的原则 ,尝试解一解 把思路分享一下( ̄▽ ̄)
  • 根据一个整数序列构造一个单链表,然后将其反转。 例如:原单链表为 2 3 4 5 ,反转之后为5 4 3 2 输入: 输入包括多组测试数据,每组测试数据占一行,第一个为大于等于0的整数n,表示该单链表的长度,后面跟着n个...
  • 单链表反转python实现

    万次阅读 2014-07-05 09:51:21
    1.循环反转单链表 循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可。   代码: class ListNode: def __init__(self,x): self.val=x; self.next=None; def ...
  • 数据结构之Java单链表反转

    万次阅读 2017-03-16 15:44:37
    用Java实现单链表反转,虽然本文研究得不是很深,但是因为是数据结构,所以必须是在对Java内存比较清楚的情况下才能真正的搞懂吃透,如果对Java内存不够清楚,那最多只能学形而不能学其内在。  首先我们要搞清楚...
  • Java实现单链表反转操作

    万次阅读 多人点赞 2018-08-24 11:57:43
    单链表是一种常见的数据结构,由一个个节点通过指针方式连接而成,每个节点由两部分组成:一是数据域,用于存储节点数据。二是指针域,用于存储下一个节点的地址。在Java中定义如下: public class Node { ...
  • 0、说在前面的话  链表结构,说难不难,说易不易,一定要亲自编程实现一下。其次就是一定要耐心,慢慢... 建立三个变量,L、M、R互相赋值迭代,并建立指向关系,从而实现单链表反转。 3、python代码实现 cla...
  • C语言单链表反转(递归,迭代),排序 前言 这篇会是关于单链表最后一篇的介绍,之前还介绍过的文章分别是: 单链表及各项操作介绍 单链表初始化 单链表打印(遍历),查询,定位,插入,删除,链表长度 单链表...
  • 单链表反转(详细图解)

    千次阅读 2019-08-20 12:26:43
    当时腾讯开发岗面试问到了,但是我xjb说了一下,就说两两交换,并找个变量存储下一个节点的位置。 但是真的写代码就感觉不是这么回事儿。后来发现思路确实有误。 其实思路应该是先找到最后一个,再一个一个往后面插...
  • Java单链表反转

    2019-03-29 16:06:50
    首先是创建一结点类,其Java代码如下: class Node { private int Data;// 数据域 private Node Next;// 指针域 public Node(int Data) { // super(); this.Data = Data; } ... public ...
  • C++实现单链表反转

    千次阅读 2019-06-08 22:17:58
    一.写在前面的话: 找工作必须是全方位重点突击,准备...《C++实现单链表反转》 实现思路: 1.如果单链表为空或者只有一个元素,那么就直接返回。 2.设置两个前后相邻的指针p,q,将p指针所指向的节点作为q所指...

空空如也

1 2 3 4 5 ... 20
收藏数 14,312
精华内容 5,724
关键字:

单链表反转