数据结构之单链表节点移动代码示例

假设有一个单链表H，要求以第一个节点为界，后续节点如果值小于第一个节点的值则将该节点移动到第一个节点的前面，如果大于第一个节点的值则移到该节点的后面。

题目本身并不难，根据题意要求就相当于是小于第一个节点的值就前移动，大于或等于就不需要动，从左到右进行遍历，直至将整个单链表遍历结束。解法比较简单，先遍历第一个节点拿到它的值，再从第二个节点开始往后遍历，如果节点的值小于第一个节点的值，则通过头插入法插入一个新的节点，并同步把当前节点删除。因为节点是一个对象，系统里面保存的都是对象的引用，所以在往单链表头插入新节点时，需要new一个新的节点出来，不能直接将头节点的下一个节点地址直接指向原来的节点地址，这样就直接出现死循环了。第一次写代码实现的时候就因为忘记了这一点，所以数据老不对，调试了半天才出来结果。具体可以参考代码

package dataStructure;
public class SingleListTest {
   public static void main(String args[]) {
	  // test1();
	   test2();
   }
   
   public static void test1() {
	   
	   Node node1 = new Node(1);
	   Node node2 = new Node(2);
	   Node node3 = new Node(3);
	   Node node4 = new Node(4);
	   SingleList list = new SingleList();
	   list.addNode(node1);
	   list.addNode(node2);
	   list.addNode(node3);
	   list.addNode(node4);
	   
	   Node node5 = new Node(5);
	   list.insertNode(node5, 1);
	   
	   list.deleteNode(2);
	   System.out.println("success!!!!");
   }
   
   public static void test2() {
	   
	   Node node1 = new Node(3);
	   Node node2 = new Node(2);
	   Node node3 = new Node(1);
	   Node node4 = new Node(4);
	   Node node5 = new Node(5);
	   SingleList list = new SingleList();
	   list.addNode(node1);
	   list.addNode(node2);
	   list.addNode(node3);
	   list.addNode(node4);
	   list.addNode(node5);
	   
	   int size = list.size;
	   Node firstNode = list.first.next;//第一个是头节点，头节点之后才是第一个节点
	   Node temp = null;
	   int data = firstNode.data;
	   int left = 2;
	   for(int i=2;i<=size;i++) {
		   temp = firstNode.next;
		   if(temp !=null) {
			   int value = temp.data;
			   if(value < data) {
				 
				   list.addHead(new Node(value));
				   left++;
				   list.deleteNode(left);
				   if(i==size) {
					   list.last = firstNode;
				   }
				   firstNode = temp;
			   }
		   }
	   }
	   System.out.println("success!!!!");
   }
}

package dataStructure;

public class SingleList {
	int size = 0;
	Node first = new Node();// 第一个节点
	Node last;// 最后一个节点
	// 在第i个元素位置添加一个新的节点
	public void insertNode(Node node, int i) {
		Node tempNode = first;
		Node nextNode = first.next;
		for (int k = 1; k <= i; k++) {
			if (k == i) {
				Node newTemp = tempNode.next;
				tempNode.next = node;
				node.next = newTemp;
				if (i == size) {
					last = node;
				}
				size++;
			} else {
				tempNode = nextNode;
				nextNode = tempNode.next;
			}
		}
	}
	// 删除第i个元素节点
	public void deleteNode(int i) {
		Node preNode = first;
		Node tempNode = first.next;
		for (int k = 1; k <= i; k++) {
			if (k == i) {
				if (i == size) {
					preNode.next = null;
					last = preNode;
				} else {
					Node nextTemp = tempNode.next;
					preNode.next = nextTemp;
				}
				size--;
			} else {
				preNode = tempNode;
				tempNode = tempNode.next;
			}
		}
	}
	// 构造单链表，尾插法
	public void addNode(Node node) {
		if (size == 0) {
			first.next = node;
			last = node;
		} else {
			Node temp = last;
			last = node;
			temp.next = node;
		}
		// 添加元素成功，则size加1
		size++;
	}
	//构造单链表，采用头插法
	public void addHead(Node node) {
		if (size == 0) {
			first.next = node;
			last = node;
		} else {
			Node temp = first.next;
			first.next = node;
			node.next = temp;
		}
		// 添加元素成功，则size加1
		size++;
	}
}