数据结构（1）链表

发表于 | 阅读数
字数统计: 1.6k | 阅读时长 ≈ 7

链表作为最基本的数据结构，在程序设计中有着非常重要的作用，其存储特点如下：可以用任意一组存储单元来存储单链表中的数据元素（存储单元可以是不连续的）,而且，除了存储每个数据元素ai的值以外，还必须存储指示其直接后继元素的信息。这两部分信息组成的数据结构元素ai的存储映像称为结点。N个结点链在一起被称为链表，当结点只包含其后继结点的信息的链表就被称为单链表，在内存中存储的方式如下图：

1570937260779

1.链表基础操作

链表最重要的操作就是向链表中插入和删除元素。

单链表的插入操作是将值为x的新结点插入到单链表的第i个结点的位置上，即插入到数据元素ai-1与ai之间。

具体步骤如下：

  1. 找到ai的引用 p
  2. 生成一个数据域为x的新结点s。
  3. 设置p.next=s。
  4. 设置s.next=a。

示意图如下：

1570939794478

单链表的删除操作是将单链表的第i个结点删去。其具体步骤如下：

1.找到ai-1的存储位置p

2.令p.next指向ai的直接后续结点（即把i从链上摘下）ai+1

下面我将给出链表基础操作的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
package mianshi;
//存储结点信息
class Node{
	Node next=null;
	int data;
	public Node(int data){
		this.data=data;
	}
}
public class linkedlist {
	Node head=null;
	//向链表中添加数据
	public void addNode(int d){
		Node newnode =new Node(d);
		if(head==null){ 
			head =newnode;
			return ;
			
		}
		Node tmp=head;
		while(tmp.next!=null){
			tmp=tmp.next;
		}
		tmp.next=newnode;
	}
	//输出链表
	public void printlist(){
		Node tmp=head;
		while(tmp!=null){
			System.out.print(tmp.data+" ");
			tmp=tmp.next;
		}
	}
	//链表的长度
	public int length(){
		int length=0;
		Node tmp=head;
		while(tmp!=null){
			length++;
			tmp=tmp.next;
		}
		return length;
	}
	//删除第index个结点
	public Boolean deleteNode(int index){
		if(index<1||index>length()){
			return false;
		}
		if(index==1){
			head=head.next;
			return true;
		}
		int i=2;
		Node prenode=head;
		Node curnode=prenode.next;
		while(curnode!=null){
			if(i==index){
				prenode.next=curnode.next;
				return true;
			}
			prenode=curnode;
			curnode=curnode.next;
			i++;			
		}
		return true;
		
	}
	//对链表排序
	public Node orderList(){
		Node nextnode=null;
		int temp=0;
		Node curnode=head;
		while(curnode.next!=null){
			nextnode=curnode.next;
			while(nextnode !=null){
				if(curnode.data>nextnode.data){
					temp=curnode.data;
					curnode.data=nextnode.data;
					nextnode.data=temp;
					
				}
				nextnode=nextnode.next;
			}
			curnode=curnode.next;
		}
		return head;
	}
	//删除重复元素
	public void deleteduplecate(){
		Node p=head;
		while(p!=null){
			Node q=p;
			while(q.next!=null){
				if(p.data==q.next.data){
					q.next=q.next.next;
				}else
					q=q.next;
			}
			p=p.next;
		}
	} 
	
		public static void main(String[] args) {
		linkedlist list=new linkedlist();
		list.addNode(3);
		list.addNode(2);
		list.addNode(4);
		list.addNode(1);
		list.addNode(5);
		System.out.println("before order:");
		list.printlist();
		list.orderList();
		System.out.println("\n"+"after order:");
		list.printlist();
		list.deleteNode(1);
		System.out.println("\n"+"after delete first:");
		list.printlist();
				
	}
}

运行结果：

before order:
3 2 4 1 5
after order:
1 2 3 4 5
after delete first:
2 3 4 5

2.删除链表中重复元素

本方法主要思路是对链表进行双重循环遍历，外循环正常遍历链表，内循环从头结点开始遍历，如果碰到和当前结点结点值相同则删除这个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
public void deleteduplecate(){
		Node p=head;
		while(p!=null){
			Node q=p;
			while(q.next!=null){
				if(p.data==q.next.data){
					q.next=q.next.next;
				}else
					q=q.next;
			}
			p=p.next;
		}
	}

3.如何检测一个链表是否有环

定义两个指针fast和slow,fast是快指针，slow是满指针，二者的初始值都指向链表头，slow每次进行一步，fast每次进行两步，两个指针同时向前移动，快指针每次都要和慢指针比较，直到当快指针等于慢指针为止，就证明这个链表有环，否则无环（fast先到尾部为null）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isloop(Node head){
		Node fast=head;
		Node slow=head;
		if(fast==null){
			return false;
		}
		while(fast!=null&&fast.next!=null){
			fast=fast.next.next;
			slow=slow.next;
			if(fast==slow){
				return true;
			}
		}
		return !(fast==null||fast.next==null);
	}

4.链表的反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void reverseIteatively(Node head){
		Node pReversedhead=head;
		Node pNode=head;
		Node pPrev=null;
		while (pNode!=null){
			Node pNext=pNode.next;
			if(pNext!=null){
				pReversedhead=pNode;
			}
			pNode.next=pPrev;
			pPrev=pNode;
			pNode=pNext;
		}
		


}

5.从尾到头输出链表

1
2
3
4
5
6
public void printlistReversely(Node plisthead){
	if(plisthead!=null){
		printlistReversely(plisthead.next);
		System.out.println(plisthead.data);
	}
}

6.两个有序单链表合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public class Node {
    /**
     * 为了方便，这两个变量都使用public，而不用private就不需要编写get、set方法了。
     * 存放数据的变量，简单点，直接为int型
     */
    public int data;
    /**
     * 存放结点的变量,默认为null
     */
    public Node next;

    /**
     * 构造方法，在构造时就能够给data赋值
     */
    public Node(int data) {
        this.data = data;
    }
}
实现类

/**
 * @auther: lawt
 * @date: 2018/11/6 09
 * @Description: 两个有序单链表合并
 */
public class MyList {
    /**
     * 递归方式合并两个单链表
     *
     * @param head1 有序链表1
     * @param head2 有序链表2
     * @return 合并后的链表
     */
    public static Node mergeTwoList(Node head1, Node head2) {
        //递归结束条件
        if (head1 == null && head2 == null) {
            return null;
        }
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        //合并后的链表
        Node head = null;
        if (head1.data > head2.data) {
            //把head较小的结点给头结点
            head = head2;
            //继续递归head2
            head.next = mergeTwoList(head1, head2.next);
        } else {
            head = head1;
            head.next = mergeTwoList(head1.next, head2);
        }
        return head;
    }

    /**
     * 非递归方式
     *
     * @param head1 有序单链表1
     * @param head2 有序单链表2
     * @return 合并后的单链表
     */
    public static Node mergeTwoList2(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return head1 != null ? head1 : head2;
        }
        //合并后单链表头结点
        Node head = head1.data < head2.data ? head1 : head2;

        Node cur1 = head == head1 ? head1 : head2;
        Node cur2 = head == head1 ? head2 : head1;

        Node pre = null;//cur1前一个元素
        Node next = null;//cur2的后一个元素

        while (cur1 != null && cur2 != null) {
            //第一次进来肯定走这里
            if (cur1.data <= cur2.data) {
                pre = cur1;
                cur1 = cur1.next;
            } else {
                next = cur2.next;
                pre.next = cur2;
                cur2.next = cur1;
                pre = cur2;
                cur2 = next;
            }
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return head;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        node1.next = node3;
        node3.next = node5;
        node2.next = node4;
//        Node node = mergeTwoList(node1, node2);
        Node node = mergeTwoList2(node2, node1);
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
}
-------------本文结束感谢您的阅读-------------
0%