删除链表的结点

问题陈述

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点，并返回删除后的链表的头节点。

思路分析

可定义一个结点，该结点的下一结点指向单链表的头结点head，以便于处理第一个元素。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val=x;
    }
}
class solustion{
    public ListNode deleteNode(ListNode head,int val){
        ListNode firstNode=new ListNode(-1);  //定义一个新节点
        firstNode.next=head;
        ListNode curr=firstNode;        //定义初始当前结点为新节点
        if(curr!=null&&curr.next!=null){
            if(curr.next.val=val){
                curr.next=curr.next.next;
            }
            curr=curr.next;
        }
        return firstNode.next;
    }
 
}

从尾到头打印链表

问题陈述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

思路分析

利用栈后进先出的特性，我们可以把链表的元素逐一存入栈，然后弹栈以输出。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//基于栈
public int[] reversePrint(ListNode head){
    Stack<ListNode> stack=new Stack<ListNode>(); //栈存储结点类型的数值
    ListNode tmp=head;
    if(tmp!=null){   //定义当前结点为head，并进行判断。
        stack.push(tmp);
        tmp=tmp.next;
    }
    int size=stack.size();
    int[] print=new int[size];
    for(int i=0;i<size;i++){
        print[i]=stack.pop().val;
        
    }
    return print;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//递归
class Solution {
    ArrayList<Integer> list=new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] num=new int[list.size()];
        for(int i=0;i<list.size();i++){
            num[i]=list.get(i);
        }
       return num;
    }
    public void recur(ListNode head){
        if(head==null) return;
        recur(head.next);
        list.add(head.val);
    }
}