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

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

本文实例讲述了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)) {

/**

* 说明两个节点相邻

ajrdpY */

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{" +

ajrdpY "stuId=" + stuId +

", name='" + name + '\'' +

", age=" + age +

", className='" + className + '\'' +

'}';

}

}

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

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。