一、查找单链表中倒数第K个节点
思路:先找出单链表中有效节点的个数length,再通过length-K找到倒数第K个节点,但是要注意头节点不算在内。
//获取链表中有效节点的个数
public int getLen(HeroNode hero){
HeroNode temp = head.next;
int length = 0;
if (temp == null){
return 0;
}
while (temp != null){
length++;
temp = temp.next;
}
return length;
}
//获取节点中倒数第K个值
public HeroNode findLastKNode(HeroNode head,int k){
HeroNode temp = head.next;
if (temp == null){
return null;
}
if (k<0 || k>getLen(head)){
System.out.println("超出链表范围");
}
for (int i = 0; i < getLen(head) - k; i++) {
temp = temp.next;
}
return temp;
}
二、反转单链表
思路:首先创建一个新的链表头部reverseHaed。并且创建两个临时变量cur,next来储存节点,遍历整个链表。
第一步,将第一个节点指向reverseHead.next,然后再将reverseHead.next指向第一个节点,这样就把第一个节点拿了下来;
第二步同第一步,将第二个节点指向reverseHead.next即原来的第一个节点,再将reverseHead.next指向第二个节点,这样第二个节点也拿了下来。
以此类推,当所有节点拿下来之后,将原先的头指针指向最后拿下的第一个节点,完成单链表的反转。
实现代码:
public void reverseNord(HeroNode head){
HeroNode cur = head.next;
HeroNode next = null;
HeroNode reverseHead = new HeroNode(0,"","");
if (cur == null || cur.next == null){
return;
}
while (cur != null){
next = cur.next;
cur.next = reverseHead.next;
reverseHead.next = cur;
cur = next;
}
head.next = reverseHead.next;
}
三、从尾到头打印链表
方式1:先将单链表进行反转操作,然后遍历即可;
但是这样会破坏原来的单链表的结构,不可取。
方式2:利用栈这个数据结构,将各个节点压入栈中,利用栈的先进后出的特点即可实现逆序打印。
public void reversePrint(HeroNode head){
if (head.next == null){
return;
}
Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode cur = head.next;
while (cur != null){
stack.push(cur);
cur = cur.next;
}
while (stack.size() > 0){
System.out.println(stack.pop());
}
}
四、按顺序合并两个链表(递归)
public class NodeList(){
int data;
NodeList next;
NodeList(int num){
data = num;
}
}
public class margeTwoLists{
public NodeList margeTwoLists(NodeList haed1,NodeList head2){
if(head1 == null){
return head2;
}
if(head2 == null){
return head1;
}
NodeList head = null;
while(head1 !=null && head2 !=null){
if(head1 => head2){
head = head2;
head.next = margeTwoLists(head1,head2.next)
}else{
head = head1;
head.next = margeTwoLists(head2,head1.next)
}
}
return head;
}
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章