前言
链表的创建、插入节点、删除节点等操作只需要20行左右的代码就能实现,其代码量适合面试。

1.1在链表头添加链表
初始时假设链表如下:

如在链表头添加一个666元素则需要先将666放进一个节点里,在节点里存入这个元素以及相应的next。

第一步:将这个666节点的next指向head,代码如下:

node.next=head

第二步:再将head指向新的节点666

head = node

图示为:

完整代码如下:

Public void addFirst(E e){
Node node = new Node(e);
node.next = head;
Head = node;
}

1.1.2在链表中间添加元素
还是原来的链表,假设需要在索引为2的位置添加元素666(此时的索引为2只是用来说明我们此时需要操作的位置,并不是真正的索引意思)。操作步骤如下:
1.创建666节点

2.使用一个变量prev来标示在需要插入节点的地方的前一个节点,初始时prev和头节点head是相同的。

对于此处我们需要在索引为2的位置插入新元素,我们只需要找到索引为2的前一个位置(索引为1),然后把prev指向索引为1节点即可。

3.进行元素添加操作
第一步先将node的next指向prev的下一个节点元素

node.next = prev.next;

第二步:再将prev的next指向node

prev.next=node

链表中间添加元素的代码:

Public void add(int Index,E e){
//此处省略判断位置是否合法
If(index == 0){
addFirst(e);
}else{
Node prev = head;
For(int I = 0;i < index -1 ; I ++){//获取到需要添加元素位置的前一个元素
Prev = prev.next;
}
Node node = new Node(e);
node.next = prev.next;
Prev.next = node;
}
}

2.反转链表,定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
遍历法:就是在链表遍历的过程中将链表反转。

代码如下:

public static Node reverseList(Node node) {
	Node pre = null;
	Node next = null;
	while (node != null) {
		next = node.next;
		node.next = pre;
		pre = node;
		node = next;
	}
	return pre;
}

发表评论

邮箱地址不会被公开。