1.求单链表中有效节点的个数
public static int getLength(HeroNode head){
HeroNode temp = head.next;//不统计头结点
int count = 0;
while (temp != null){
count++;
temp = temp.next;
}
return count;
}
2.新浪面试题——寻找链表倒数第k个节点
public static int getLength(HeroNode head){
HeroNode temp = head.next;//不统计头结点
int count = 0;
while (temp != null){
count++;
temp = temp.next;
}
return count;
}
public static HeroNode findNode(HeroNode head,int k){
if (head.next == null)
return null;
int index = getLength(head)+1-k;//顺序索引
if (index > getLength(head) || index <= 0)
return null;
HeroNode temp = head;
while (index > 0){
temp = temp.next;
index--;
}
return temp;
}
3.腾讯面试题——单链表的反转(头插法)
public static void reverseList(HeroNode head){
if (head.next == null || head.next.next == null)
return;
HeroNode cur = head.next;//辅助变量,用于遍历原来的链表
HeroNode next = null;//指向当前节点的下一节点
HeroNode reverseHead = new HeroNode(0,"","");
//遍历原来的链表,每遍历一个节点就将其取出,并放在新的链表的最前端
while (cur != null){
next = cur.next;
cur.next = reverseHead.next;//将cur的下一节点指向新的链表的最前端
reverseHead.next = cur;//将reverseHead和cur连接起来
cur = next;//cur后移
}
head.next = reverseHead.next;
}
4.百度面试题——从尾到头打印单链表
方式1:反向遍历,先反转再打印,但是会破坏原本链表结构,不建议。
方式2:栈,不会改变链表原本的结构
public static void reversePrint(HeroNode head){
if (head.next ==null)
return;
Stack record = new Stack<>();
HeroNode temp = head.next;
while (temp != null){
record.push(temp);
temp = temp.next;
}
while (!record.isEmpty()){
System.out.println(record.pop());
}
}
5.合并两个有序的链表,合并之后的链表依旧有序
leetcode——剑指offer25
//递归方法
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
else if (l2 == null)
return l1;
else if ( l1.val < l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}
else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
//迭代方法
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode preHead = new ListNode(-1);
ListNode pre = preHead;
while (l1 != null && l2!=null){
if (l1.val <= l2.val){
pre.next = l1;
l1 = l1.next;
}
else {
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
}
pre.next = l1 == null ? l2:l1;
return preHead.next;
}



