9.java单链表初学代码复现及一些不值一提的小问题（2）

首先写完了update和delete函数，在之前的铺垫下。倒是不难，结构和之前的都相同，遍历找到节点后处理该节点。代码如下

public void update(teamNode node){

        teamNode temp=head;

        boolean flag=false;

        while(true){

            if (temp.no== node.no){

                flag=true;

                break;

            }

            if(temp.next==null) break;

            temp=temp.next;

        }

        if(!flag){

            System.out.println("无该名次队伍");

        }else {

            temp.name= node.name;

            temp.point=node.point;

        }

    }

    public void delete(int n){

        teamNode temp=head;

        boolean flag=false;

        while(true){

            if(temp.next==null) break;

            if (temp.next.no== n){

                flag=true;

                break;

            }

            temp=temp.next;

        }

        if(!flag){

            System.out.println("无该名次队伍");

        }else {

            temp.next=temp.next.next;

        }

    }

此外，还有一些关于单链表的题：

1、单链表中的有效节点数

思路为遍历获取节点个数，带头节点的话需要不计入。步骤为：传入头节点，判断是否为空链表，不为则创建辅助节点，遍历整个链表。

public static int getlength(teamNode node){

        if(node.next==null){

            return 0;

        }

        int len=0;

        teamNode temp=node;

        while (temp!=null){

            len++;

            temp=temp.next;

        }

        return len;

    }

2、查找单链表中的倒数第k个节点。

方法参数为头节点和一个int代表倒数第几个节点。得到链表长度后，判断此节点是否存在。若存在则遍历链表到（len-k）个即可得到该节点。未找到的话返回null

public static teamNode findnode(teamNode head,int k){

        if(head.next==null){

            return null;

        }

        int len=getlength(head);

        if(k<=0||k>len) return  null;

        teamNode temp=head.next;

        for (int i=0;i<len-k;i++){

            temp=temp.next;

        }

        return temp;

    }

除了此思路还有一种是用双指针，让两个指针相隔k个位置，当后方的指针指到空时，前指针则指向倒数第k个节点。

3、单链表的反转

思路简单来说就是新建一个头节点，将原链表的节点一个个取出，用头插法插入新链表，最后将原头节点与链表相连接。

仔细说分为一下几步，先创建一个新的头节点，然后开始遍历原链表，拿出节点后永远放在新链表的头节点之后，即新链表有效数据的第一个，最后将原链表的头节点的next连到新链表的第一个节点上即可。

此函数最开始不仅要判断原链表是否为空，若原链表只有一个节点，其也不用反转，直接返回原链表即可。

在遍历时，因为被遍历到的节点需要“拿出来”去改变其next，所以需要一个node来临时保存其next，让我们能获得下一个节点。因为被遍历到的节点的next要去连接新链表的值，若不保存，原来指向的那个节点还未被遍历到，覆盖后就无法得到那个节点了。

所以在此处要创建三个节点，一为辅助节点temp，一为临时保存的next节点，一为新链表的头节点。

public static void reverse(teamNode head){

        if(head.next==null||head.next.next==null){

            return;

        }

        teamNode temp=head.next;

        teamNode next=null;

        teamNode rehead=new teamNode(0,"","");

        while (temp!=null){

            next=temp.next;

            temp.next=rehead.next;

            rehead.next=temp;

            temp=next;

        }

        head.next=rehead.next;

    }

4、从尾到头打印单链表

可以先利用上面的函数反转了再打印，但会导致原链表彻底变化（当然打印完再转一遍也不是不行。。）但此处选择用栈 stack来解决。利用其先进后出的原理来解决该题。其中，利用Stack<teamNode> stack=new Stack<teamNode>();可创建栈，栈中的数据形式可自定义，此处为node。

其中，stack.add（）stack.push()为入栈，

stack.pop()为取出并返回栈顶的第一个数据。

因为题目要求为打印，因此不用形成链表，有输出即可。

public  static void reprint(teamNode head){

        if (head!=null){

            return;

        }

        Stack<teamNode> stack=new Stack<teamNode>();

        teamNode temp=head.next;

        while (temp!=null){

            stack.push(temp);

            temp=temp.next;

        }

        while (stack.size()>0){

            System.out.println(stack.pop());

        }

    }

写完这些我可以说是对单链表确实的有了更深的理解，在之前就有所了解数据结构的基础上，可以说是对java中的链表有了进一步的了解。但当看到最后一题用的栈时，我在想java中是不是也有这样已经给我们写好的基本链表定义和一些函数呢，不然难道每次需要用到链表的时候都需要重新这样从头开始定义一遍嘛。很显然，我的懒鬼想法是大多数人的想法，java当然有直接的定义和预先写好的函数。但对于此些API和定义我还尚且不太清楚。

巴特西

9.java单链表初学代码复现及一些不值一提的小问题（2）

最新文章

热门文章