本文共 5019 字,大约阅读时间需要 16 分钟。
今日份要点,叮~~
链表的创建和遍历,统计节点个数,查找倒数第k个节点(查找中间节点于此类似),合并两个链表(个人感觉有点归并的意思),单链表从尾到头打印(使用栈和递归方法)
package lianbiao;
import java.util.Stack;
class Node{
int data;//数据域 Node next;//指针域 public Node(int data) { this.data = data; } } public class Link_List{ public Node head; public Node current; //添加节点 public void add(int data) { //判断链表是否为空,若为空则尚未创建,把新的结点赋给头节点 if(head==null) { head = new Node(data); current = head; } else { //创建新的节点,放在当前节点后面 current.next = new Node(data); //把链表的当前索引向后移动一位 current = current.next; } } //打印链表 public void print(Node node) { if(node==null) { return; } current = node; while(current!=null) { System.out.print(current.data+" "); current = current.next; } } //求单链表中节点个数 public int getLength(Node head) { if(head==null) { return 0; } int length=0; while(head!=null) { length++; head = head.next; } return length; } //查找链表中倒数第k个节点 //方法一:先遍历一次将节点个数统计出,然后在将指针移动到要输出节点处,输出结果,时间复杂度O(n) public int findLastNode(int index) { int size=0; if(head == null) { return -1; } current = head; while(current!=null) { size++; current = current.next; } current=head; for(int i=0;i<size-index;i++) { current=current.next; } return current.data; } //方法二:定义两个指针first和second,首先让两个节点都指向第一个节点,然后让second节点往后挪k-1个位置, //此时first和second就间隔了K-1个位置,然后整体向后移动,直到second节点走到最后一个节点的时候,此时first //节点指向的位置就是倒数第k个节点的位置,时间复杂度为O(n) public Node findLastNode(Node head,int index) { if(head==null||index==0) { return null; } Node first = head; Node second = head; //让second节点向后挪动index个位置 for(int i=0;i<index;i++) { second = second.next; //判断查找的那个节点是否已经超出了链表结点个数 if(second==null) { return null; } } //让first和second节点整体向后移动,直至second节点为null while(second!=null) { first = first.next; second = second.next; } //当second为空的时候,此时first指向的节点就是我们要找的节点 return first; } //查找单链表中的中间节点,同上述方法二,但需要判断一下链表节点奇数、偶数 //合并两个有序的单链表,合并之后的链表依然有序 //方法一:挨个比较链表1和链表2,类似于归并排序 //需要考虑的情况有: //两个链表都为空,和其中一个为空的情况,只需要O(1)的空间,时间复杂度为O(max(len1,len2)) public Node mergeLinkList(Node head1,Node head2) { if(head1==null&&head2==null) { return null; } if(head1==null){ return head2; } if(head2==null) { return head1; } Node head;//新链表的头节点 Node current;//current节点指向head1和head2中较小的数据,得到head节点 if(head1.data<head2.data) { head = head1; current = head1; head1 = head1.next; }else { head = head2; current = head2; head2 = head2.next; } while(head1!=null && head2!=null) { if(head1.data < head2.data) { current.next = head1;//新链表中,current指针的下一个节点对应较小较小的那个数据 current = current.next;//current指针下移 head1 = head1.next; } else { current.next = head2; current = current.next; head2 = head2.next; } } //合并剩余元素 if(head1!=null) { current.next = head1; } if(head2!=null) { current.next = head2; } return head; } //从尾到头打印单链表:这个问题涉及到颠倒顺序问题,故应该想到栈,后进先出 //方法一:自己新建一个栈 public void reversePrint(Node head) { if(head==null) { return; } Stack<Node> stack = new Stack<Node>(); Node current = head; //将链表的所有节点压栈 while(current!=null) { stack.push(current); current = current.next; } while(stack.size()>0) { System.out.println(stack.pop().data);//出栈操作 } } //方法二:使用系统的栈:递归 public void reversePrintSystem(Node head) { if(head==null) { return; } reversePrintSystem(head.next); System.out.println(head.data); } public static void main(String[] args) { // TODO 自动生成的方法存根 Link_List list = new Link_List(); for(int i=0;i<10;i++) { list.add(i); } //list.print(list.head); } } 单链表的反转问题,总结了三种方法:package digui;
import java.util.LinkedList;
public class ReverseLink {
static class Node{
Integer data; Node next; } static Node readyNode() { Node linkNode1 = new Node(); linkNode1.data = 1; Node linkNode2 = new Node(); linkNode2.data = 2; Node linkNode3 = new Node(); linkNode3.data = 3; Node linkNode4 = new Node(); linkNode4.data = 4; Node linkNode5 = new Node(); linkNode5.data = 5; Node linkNode6 = new Node(); linkNode6.data = 6; linkNode1.next = linkNode2; linkNode2.next = linkNode3; linkNode3.next = linkNode4; linkNode4.next = linkNode5; linkNode5.next = linkNode6; return linkNode1; } //1、迭代实现,创建一个新链表,从头部开始复制至新链表 static Node reverseNode1(Node linkNode) { if(linkNode==null||linkNode.next==null) { return linkNode; } Node p =linkNode,newNode=null; while(p!=null) { Node temp = p.next; p.next = newNode; newNode = p; p = temp; } return newNode; } //2、递归实现链表的反转:递归到链表尾部再开始逐层反转 static Node reverseNode2(Node linkNode) { if(linkNode==null||linkNode.next==null) {//到达链表尾部 return linkNode; } else { Node node = reverseNode2(linkNode.next); linkNode.next.next = linkNode;//相当于将节点从原来的1指向2,变为了2指向1 linkNode.next = null;//为了断开现在指针的链接,防止出现环 return node; } } //3、遍历实现,借助两个指针实现指向:从头节点开始改变指向 static Node reverseNode3(Node linkNode) { Node previousNode = null; Node currentNode = linkNode; Node headNode = null; while(currentNode!=null) { Node nextNode = currentNode.next; if(nextNode==null) { headNode = currentNode; } currentNode.next = previousNode; previousNode = currentNode; currentNode = nextNode; } return headNode; } public static void main(String[] args) { // TODO 自动生成的方法存根 Node node = readyNode(); node = reverseNode1(node); while(node!=null) { System.out.print(node.data+" "); node = node.next; } } } 明天又是新的一天!UP,UP,UP~~转载地址:http://preii.baihongyu.com/