Java实现双链表互相交换任意两个节点的方法示例

2019-11-26 10:57:49

字体：大中小

来源：转载

供稿：网友

本文实例讲述了Java实现双链表互相交换任意两个节点的方法。分享给大家供大家参考，具体如下：

概述：

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

思路：

1、确定两个节点的先后顺序
2、next、prev互相交换顺序以及将换向前方的节点与之前的节点对接。（1.prev.next = 2）
3、判断是否相邻

实现代码：

链表类：

public class SLink {  public SNode head;  public SLink() {    this.head = new SNode();  }  public boolean interChangeById(int id1,int id2) {    SNode s = head;    SNode node1 = null,node2 = null;    int node1Count,node2Count;    node1Count = node2Count = 0;    if(id1 == id2) {      return true;    }    /**     * 向下遍历     */    while (s.next != null) {      s = s.next;      node1Count ++ ;      if(s.student.stuId == id1) {        /**         * 记录节点1         */        node1 = s;        break;      }    }    s = head;    while (s.next != null) {      s = s.next;      node2Count ++ ;      if(s.student.stuId == id2) {        /**         * 记录节点2         */        node2 = s;        break;      }    }    if(node1 != null && node2 != null) {      SNode temp = new SNode();      /**       * node1在后       */      if(node1Count > node2Count) {        temp.next = node1.next;        temp.prev = node1.prev;        /**         * 记录那个节点就先处理那个节点         * 1、交换next         * 2、交换prev         * 3、设置之前节点的next（对接）         */        node1.next = node2.next;        node1.prev = node2.prev;        node2.prev.next = node1;        if(node1.next.equals(node1)) {          /**           * 说明两个节点相邻           */          node1.next = node2;          node2.next = temp.next;          node2.prev = node1;        }else {          /**           * 说明节点不相邻           */          node2.next = temp.next;          node2.prev = temp.prev;          temp.prev.next = node2;        }      }else {        /**         * node1在前         */        temp.next = node2.next;        temp.prev = node2.prev;        node2.next = node1.next;        node2.prev = node1.prev;        node1.prev.next = node2;        if(node2.next.equals(node2)) {          node2.next = node1;          node1.next = temp.next;          node1.prev = node2;        }else {          node1.next = temp.next;          node1.prev = temp.prev;          temp.prev.next = node1;        }      }      return true;    }    return false;  }  public void displayStudent() {    SNode s = head;    while (s.next != null) {      s = s.next;      System.out.println(s.student);    }  }}

节点类：

public class SNode {  public Student student;  public SNode next;  public SNode prev;  public SNode(Student student, SNode prev,SNode next) {    this.student = student;    this.next = next;    this.prev = prev;  }  public SNode() {    this.student = null;    this.next = null;    this.prev = null;  }}

Student类：

public class Student {  public int stuId;  public String name;  public int age;  public String className;  public Student(int stuId, String name, int age, String className) {    this.stuId = stuId;    this.name = name;    this.age = age;    this.className = className;  }  public int getStuId() {    return stuId;  }  public void setStuId(int stuId) {    this.stuId = stuId;  }  public String getName() {    return name;  }  public void setName(String name) {    this.name = name;  }  public int getAge() {    return age;  }  public void setAge(int age) {    this.age = age;  }  public String getClassName() {    return className;  }  public void setClassName(String className) {    this.className = className;  }  @Override  public String toString() {    return "Student{" +        "stuId=" + stuId +        ", name='" + name + '/'' +        ", age=" + age +        ", className='" + className + '/'' +        '}';  }}

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

上一篇：application作用域实现用户登录挤掉之前登录用户代码

下一篇：分享一个简单的java爬虫框架