一、链表题目
1、从尾到头打印链表
- 使用栈（也可以使用数组，逆序输出）
/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */ import java.util.Stack; import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> list = new ArrayList<>(); Stack<ListNode> stack = new Stack<>(); while(listNode!=null){ stack.push(listNode); listNode = listNode.next; } while(!stack.isEmpty()){ list.add(stack.pop().val); } return list; } }
- 反转链表再打印
关键点：要注意画图
import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> list = new ArrayList<>(); ListNode pre = null; // 定义前驱节点 ListNode cur = listNode; // 定义当前节点 while(cur!=null){ ListNode next = cur.next; // 定义后继节点 cur.next = pre; pre = cur; cur = next; } ListNode head = pre; while(head!=null){ list.add(head.val); head = head.next; } return list; } }
- 递归打印链表
递归到链表的尾部，再依次将链表结点存入数组中
算法实现：
变量：先创建一个list数组
递归结束条件：当链表结点为null，listNode==null。
结果：list即为逆序排列链表数值后的数组
import java.util.ArrayList; public class Solution { ArrayList<Integer> list = new ArrayList<>(); public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { if(listNode!=null){ printListFromTailToHead(listNode.next); list.add(listNode.val); } return list; } }
2、反转链表
通过三个指针轮流交替 的迭代方法
public class Solution { public ListNode ReverseList(ListNode head) { if(head==null || head.next == null){ return head; } ListNode pre = null; ListNode cur = head; while(cur!=null){ ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } }
迭代方法
/** *递归实现单链表反转 * @param list 为传入的单链表 */ public static Node recursiveList(Node list){ // 如果链表为空 或者 链表中只有一个节点,直接返回 // 也是递归结束的条件 if (list == null || list.next == null) return list; Node recursive = recursiveList(list.next); // 将 list.next.next 指针指向当前链表 list list.next.next = list ; // 将 list.next 指针指向 null list.next = null; // 返回反转之后的链表 recursive return recursive; }
3、合并两个排序的链表
非递归 版本
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { ListNode newHead = new ListNode(0); ListNode result = newHead; while(list1!=null&&list2!=null){ if(list1.val>=list2.val){ newHead.next = list2; list2 = list2.next; }else{ newHead.next = list1; list1 = list1.next; } newHead = newHead.next; } if(list1!=null){ newHead.next = list1; } if(list2!=null){ newHead.next = list2; } return result.next; } }
