精华内容
下载资源
问答
  • 链表的逆序

    2019-03-21 11:17:30
    链表的逆序就是剑指offer中从尾到头打印链表 不难想出就是利用栈的使用,从链表的头部开始依次将元素放入栈中,然后遍历结束后,将栈中的元素全部出栈,即为逆序,让我们看看代码实现 因为go中不提供栈,所有我下面...

    链表的逆序就是剑指offer中从尾到头打印链表

    不难想出就是利用栈的使用,从链表的头部开始依次将元素放入栈中,然后遍历结束后,将栈中的元素全部出栈,即为逆序,让我们看看代码实现
    因为go中不提供栈,所有我下面用切片代替,建议大家练习时,可以用栈实现

    func PrintList(node *ListNode){
    	res:=[]int{}
    	if node==nil{
    		return
    	}
    	for node!=nil{
    		res=append(res,node.Val)
    		node=node.Next
    	}
    	for i:=len(res)-1;i>=0;i--{
    		fmt.Println(res[i])
    	}
    }
    

    有的同学可能说了,没有别的办法吗,当然有了,别忘了栈的思想是可以递归实现的,递归到最后一个元素后,返回打印这个节点,看看代码

    func printList(node *ListNode){
    	if node==nil{
    		return
    	}
    	if node.Next==nil{
    		fmt.Println(node.Val)
    		return
    	}
    	printList(node.Next)
    	fmt.Println(node.Val)
    }
    

    使用递归,可以很明显看出代码确实很简洁,但是使用这个方法不一定就好,当一个链表非常大时,可想递归的深度非常可怕,没有使用栈的鲁棒性更好。

    展开全文
  • 链表的逆序输出

    2017-12-01 22:47:40
    【数据结构与算法】给定一个链表及该链表的头结点,要求实现链表的逆序输出 思考:可以用到栈的先入后出的特点,把链表的节点顺序入栈,然后一次出栈,这样就实现了链表的逆序输出 相关代码:

    【数据结构与算法】给定一个链表及该链表的头结点,要求实现链表的逆序输出

    1.利用数据结构栈的先入后出的特点,通过将链表的所有节点依次入栈和依次出栈,完成链表的逆序输出,但这种做法,并未改变链表的节点(并未完成聊表翻转),只是简单地将链表所有节点逆序输出  

    相关代码:

    package com.csu;
    
    import java.util.List;
    import java.util.Stack;
    
    public class ReversLinkedList {
    
        public static class ListNode{
            //节点的值
            int val;
            //下一节点
            ListNode next;
        }
    
        //逆序输出,在方法中传入链表的头结点
        public static void printListInversely(ListNode head){
            Stack<ListNode> stack = new Stack<>();
    
            while(head != null){//当头节点不为空的时候使链表进栈
                stack.push(head);
                head = head.next;
            }
    
            ListNode temp;
            //进栈之后,依次出栈
            while(!stack.isEmpty()){
                temp = stack.pop();
                System.out.print(temp.val+"  ");
            }
    
        }
        public static void main(String[] args) {
    	ListNode root = new ListNode();
            root.val = 1;
            root.next = new ListNode();
            root.next.val =2;
            root.next.next = new ListNode();
            root.next.next.val = 3;
            root.next.next.next = new ListNode();
            root.next.next.next.val=4;
            root.next.next.next.next = new ListNode();
            root.next.next.next.next.val=5;
    
            printListInversely(root);
        }
    }
    

     

    2.迭代法

     

    解题思路:迭代的思路就是将当前结点、当前结点前一结点、当前结点的下一节点三个结点当做一个单元,先在该单元中完成链表的逆序,然后将这个单元滑窗式地往后移动,直到当前结点为原链表的尾结点,然后再补上新的头结点。

    代码:

    public ListNode reverse(ListNode head) {
    
            ListNode pre = null;//当前结点的前结点
            ListNode cur = head;//当前结点,从头结点开始迭代
    
            while (cur !=null) {
                ListNode tmp = cur.next;//用tmp记录当前结点的下一节点,在后续结点后移的时候需要
                cur.next = pre;//将当前结点的指针域指针指向前一节点
    
                //开始往后迭代
                pre = cur;//当前结点变为下次迭代的前节点
                cur = tmp;//当前结点的下一节点为下次迭代的当前结点
            }
            return pre;//最后的pre结点即为逆转后链表的新头结点
        }

    3.递归法

    递归法的思想与迭代法类似,通过递归到达原链表的尾结点,然后从尾结点开始进行翻转,直到所有的节点翻转完成

    public ListNode reverse1(ListNode head) {
            //递归设定递归的跳出条件
            if (head == null || head.next == null) {//如果链表为空,或者链表只有一个结点,即返回head
                return head;
            }
    
            ListNode next = head.next;//next记录当前结点的下一节点
    
            ListNode newHead = reverse1(next);//递归
    
            head.next.next = head;//当前结点与该结点的下一节点逆序,代码理解最好为:首先head.next是当前结点的下结点,(head.next).next即为下一结点的指针域指向当前结点,翻转的第一步
            head.next = null; //当前结点head的指针域(指向下一节点)置空,翻转的第二步
    
            return newHead;//最后返回新的头结点
        }

     

    展开全文
  • 1. 传入一个链表的头节点 2. 生成一个新的空结点(pNew),后续作为链表的结点备份 3. 用一个指针(pNext)指向当前头节点的下一个节点,作为记录保存 4. 把头节点的下一个节点指向新结点(pNew) 5. 将pNew更新为...

    1 整个链表的逆序

    在这里插入图片描述

    1.1思路

    1. 传入一个链表的头节点
    2. 生成一个新的空结点(pNew),后续作为链表的结点备份
    3. 用一个指针(pNext)指向当前头节点的下一个节点,作为记录保存
    4. 把头节点的下一个节点指向新结点(pNew)
    5. 将pNew更新为当前头节点的指针
    6. 将头节点更新为pNext
    7. 重复3 4 5 6过程,直到头节点指针指向空
    8. 此时新结点pNew的指针即为链表逆序翻转后的头指针
    9. 返回pNew

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    1.2代码实现(C++)

    struct ListNode
    {
     int val;
     ListNode* next;
     ListNode(int x) :val(x), next(NULL) {}//初始化结点
    };
    
    class Solution
    {
    public:
     static ListNode* reverseList(ListNode* head)
    {
    	  ListNode* pNew = NULL;
    	  while (head)//当前头节点为空时跳出循环
     	 {
      		 ListNode* pNext = head->next;
    	  	 head->next = pNew;
    	  	 pNew = head;
    	  	 head = pNext;
        	 }
        	 //循环结束后,此时的头节点为空,所以返回头节点的上一个结点pNew
     	 return pNew;
     }
     
     static void printList(ListNode* head)//打印结点
    {
    	  while (head)
    	  {
    	  	 cout << head->val;
    	  	 head = head->next;
    	  }
    }
    }/******测试*****/
    void main()
    {
    	 ListNode a(1);
    	 ListNode b(2);
    	 ListNode c(3);
    	 ListNode d(4);
    	 ListNode e(5);
    	 a.next = &b;
    	 b.next = &c;
    	 c.next = &d;
    	 d.next = &e;
    	 ListNode* head = &a;
    	 Solution::printList(head);
    	 cout << endl;
    	 head = Solution::reverseList(head);
    	 Solution::printList(head);
    	 cout<<endl;
    	 return}

    在这里插入图片描述

    2 链表的一部分实现逆序

    2.1思路

    • 实现一段链表的部分逆序
      已知链表的头节点指针head,将链表从位置m到n逆序
      在这里插入图片描述
      - 步骤实现
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述

    2.2代码实现

    ListNode* reverseList(ListNode* head, int m, int n)//反转m-n处的链表
    {	
    	int change_len = n - m + 1;//计算需要逆序的节点个数
    	  ListNode* InitHead = head;//备份初始头节点
     	 ListNode* pre_head = NULL;
     	 while (head&&--m)//找到要反转的起始节点,并把起始节点m的前结点备份到pre_head中
     	 {
     	 	pre_head = head;
      	        head = head->next;
     	 }
    	 ListNode* reverse_lastNode = head;//备份反转后的最后一个链表的结点
    	  ListNode* newNode = NULL;//翻转链表过程中使用的辅助结点
    	  while (head&&change_len)//反转链表m-n
    	  {
    	        ListNode* pNext = head->next;
     		head->next = newNode;
     		newNode = head;
     		head = pNext;
     		change_len--;
    	  }
    	  reverse_lastNode->next = head;//翻转后的最后一个结点的下一个结点指向逆序前的第n个结点的下一个节点
     	 //判断第m个节点的上一个结点是否为空,若为空,则新链表的头节点为反转后的头节点
    	 //若不为空则将pre_head->指向反转后的头节点newNode
    	  if (pre_head)
    	  {
      		pre_head->next = newNode;
     	  } 
     	 else
     	  {
     		InitHead = newNode;
     	  }
     	 return InitHead;
    }
    展开全文
  • 单向链表的逆序

    2021-06-13 20:17:15
    1.用带头结点的单向不循环链表的逆序,遇到问题是:每次逆序完,只显示首节点的数据,好像是没有逆序,而且中间环节出了问题 2.后来修改完程序,就正常了。 问题的原因是:在赋值给tmp后,应该保存pfirst后面的节点...

    1.用带头结点的单向不循环链表的逆序,遇到问题是:每次逆序完,只显示首节点的数据,好像是没有逆序,而且中间环节出了问题
    在这里插入图片描述在这里插入图片描述2.后来修改完程序,就正常了。
    在这里插入图片描述在这里插入图片描述问题的原因是:在赋值给tmp后,应该保存pfirst后面的节点。而先操作tmp->next赋值,其后的节点为NULL了,因此,在后面再给pfirst赋值就是NULL了,故只显示第一个节点。希望对你有用。

    展开全文
  • 链表的逆序输出(链表) 题目描述 按数字输入顺序创建单链表。不可借助数组、容器,不可改变原链表、不可开辟新结点空间(输出链表时)。编程实现单链表的逆序输出。 输入 测试次数t 每组测试数据一行,格式如下: ...
  • 第二章 线性表—链表的逆序 数据结构基础代码 (严蔚敏 人邮教育出版社) #include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; //写一个函数,把链表逆序 typedef ...
  • 链表的逆序:链表的只逆序输出,链表不逆序,第二种是链表的逆序。、 面试中经常考察链表的逆序。 https://www.jianshu.com/p/8b6f4dbe497e https://blog.csdn.net/liu583685/article/details/78125454 参考博客...
  • 链表的逆序操作

    2019-08-07 16:37:44
    链表的逆序操作: 代码如下: #include<stdio.h> #include<malloc.h> #include<string.h> typedef struct _STU//定义一个结构体,链表的每一个节点都为此类型。 { int id;//学号 char name[32];...
  • 实现链表的逆序

    2019-09-03 18:50:04
    实现链表的逆序,HEAD->0->1->2->3->4->5,逆序转换为:HEAD->5->4->3->2->1->0 解题思路 1.将每一个节点的next设置为它的前驱节点(注意对首尾节点的处理) 2.从第二个节点...
  • 练手>链表的逆序打印
  • 实现链表的逆序主要的思路有如下: 1、通过头插法来实现的。通过遍历原来的链表,将遍历得到的每一个节点都插入到新链表的头结点,然后遍历新链表,得到的就是链表的逆序了。 实现链表逆序的代码: 过程分析: 看到...
  • 链表的逆序和排序

    2020-03-02 23:20:29
    链表的逆序 程序中的结构体定义: typedef struct people { int num; char name[32]; double wage; struct people *next; }PEO; 原理图 代码实现: PEO * reverse_link(PEO *head) { if (head == NULL)/判断...
  • python实现链表的逆序

    2020-07-28 23:05:28
    python实现链表的逆序 腾讯笔试题 题目描述: 给定 一个带头结点的 单链表,请将其逆序。即如果单链表原来为head->1一>2->3->4->5>6 >7,那么逆序后变为 head一>7一>6一>5->4->3...
  • 前几天一位小伙伴去面试,被要求现场写如何实现链表的逆序?写完一种问还有没有其他方式?今天咱们就来聊聊到底如何实现链表的逆序以及有哪些方法?(文中的链表是单链表)给定一个带头节点的单链表...
  • 链表的逆序 首先,我们来看看单链表的逆序(双向链表操作一样的)。操作简单,我就直接贴代码了。 void reverse(node *head) //链表逆序 { node *p=head->next; node *q; while(p->next!=NULL) //!!...
  • 如何实现链表的逆序

    千次阅读 2019-04-11 20:45:36
    如何实现链表的逆序? 下面介绍了两种方法:1.就地逆序法 2.插入法 单链表数据结构 /** * @program: 算法与数据结构 * @description: 单链表数据结构 * @author: 粉刷匠 * @create: 2019-04-11 20:02 ...
  • java版的单向链表的逆序输出

    千次阅读 2014-11-07 18:36:32
    java版的单向链表的逆序输出
  • Java链表的逆序(详解)

    2019-10-05 16:40:33
    链表的逆序算法: ```java public ListNode reverseList(ListNode head) { if(head == null){ // return null; } if(head.next == null){ return head; } ...
  • 剑指offer 链表的逆序

    2015-07-08 22:24:15
    链表的逆序应该是面试题中比较经典的题目了。 自己也写过了很多的变,还是不能深刻的理解。特写博客记录。 链表的逆序一般有两种写法:循环写法和递归写法 循环写法:(非常的简单) 思路就是:用一个临时指针记录...
  • 线性链表的逆序操作

    千次阅读 2012-11-29 14:56:49
    关于线性链表的逆序可用循环和递归的两种方式完成,逆序的递归方式比较难理解,主要是返回头结点的问题。 链表节点定义如下: //定义线性链表结点 typedef struct node { int data; struct node *link; }LNode...
  • 链表的逆序输出 按值删除 归并排序 链表的逆序输出: void Reverse(PNODE * ppHead) { if (!(NULL == *ppHead || NULL == (*ppHead)->next)) { PNODE p1, p2, p3; p1 = *ppHead; p2 = p1->next; p3 ...
  • [算法]链表的逆序遍历节点

    千次阅读 2014-12-13 15:22:40
    [算法]链表的逆序遍历节点

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,386
精华内容 2,554
关键字:

链表的逆序