链表算法面试题---链表
本文共 11571 字，大约阅读时间需要 38 分钟。
前言
一般链表的基础题算法都很简单，但却是常见的面试题，因为链表能够考察面试者的编码能力，往往很容易想到解题方式，却写不出来。
下面总结了几道常见的初级题，可以反复练习，提高自己的编码能力。
先准备两个对象，一个单链表，一个双链表
单链表
public class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } @Override public String toString() { return "ListNode{" + "val=" + val + ", next=" + next + '}'; }} 双链表
public class DoubleListNode{ public T data; public DoubleListNode last; public DoubleListNode next; public DoubleListNode(T data) { this.data = data; } @Override public String toString() { return "DoubleListNode{" + "data=" + data + ", next=" + next + '}'; }}
1、单链表反转
单链表反转，经典且基础的链表题。
举例：
原链表：1-2-3-4-5 反转后：5-4-3-2-1public class Code_01 { public static void main(String[] args) { ListNode n = new ListNode(); ListNode head = n; for (int i = 1; i <= 5; i++) { n.next = new ListNode(i); n = n.next; } System.out.println("原链表：" + head); ListNode listNode = reverseList(head); System.out.println("反转后：" + listNode); } private static ListNode reverseList(ListNode head) { ListNode pre = null; ListNode next; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; }} 
2、双链表反转
public class Code_02 { public static void main(String[] args) { DoubleListNode n1 = new DoubleListNode(1); DoubleListNode n2 = new DoubleListNode(2); n1.next = n2; n2.last = n1; DoubleListNode n3 = new DoubleListNode(3); n2.next = n3; n3.last = n2; System.out.println("原链表：" + n1); DoubleListNode listNode = reverseDoubleList(n1); System.out.println("反转后：" + listNode); } private static DoubleListNode reverseDoubleList(DoubleListNode head) { DoubleListNode pre = null; DoubleListNode next; while (head != null) { next = head.next; head.next = pre; head.last = next; pre = head; head = next; } return pre; }} 
3、删除链表中的某类节点
举例：
原链表：1-2-3-4-5 删除value=2的节点 结果：1-3-4-5原链表：1-2-3-3-3-4-5
删除value=3的节点 结果：1-2-4-5原链表：1-1-2-3-4-5
删除value=1的节点 结果：2-3-4-5public class Code_03 { public static void main(String[] args) { ListNode n = new ListNode(); ListNode head = n; for (int i = 1; i <= 5; i++) { n.next = new ListNode(i); n = n.next; } System.out.println("原链表：" + head); ListNode node = deleteNode(head, 3); System.out.println("删除后：" + node); } private static ListNode deleteNode(ListNode head, int value) { //处理head本身就是要删除的节点 while (head != null) { if (head.val != value) { break; } head = head.next; } //始终记录前一个节点，和当前节点的指针，如果当前节点就是要删除的节点时，则让前一个节点指向当前节点的下一个节点，即完成了删除 ListNode cur = head; ListNode pre = null; while (cur != null) { if (cur.val == value) { pre.next = cur.next; } else { pre = cur; } cur = cur.next; } return head; }} 
4、删除重复元素1
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
举例：
原链表: 1->1->2->3->3 删除后: 1->2->3public class Code_05 { public static void main(String[] args) { Code_05 c = new Code_05(); ListNode n = new ListNode(); ListNode head = n; for (int i = 1; i <= 5; i++) { n.next = new ListNode(i); n = n.next; if (i % 2 == 0) { n.next = new ListNode(i); n = n.next; } } System.out.println("原链表：" + head); System.out.println("删除后：" + c.deleteDuplicates(head)); } /** * 通过不断移动cur，判断当前cur的值与cur.next的值是否相等，如果相等，则只改变cur.next，并让其指向下一个节点，就等于跳过了cur.next的节点 * 如果不相等，则移动cur节点位置到cur.next上。 * @param head * @return */ public ListNode deleteDuplicates(ListNode head) { ListNode cur = head; while (cur != null && cur.next != null) { if (cur.val != cur.next.val) { cur = cur.next; } else { cur.next = cur.next.next; } } return head; }} 5、删除重复元素2
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。
举例：
原链表: 1->2->3->3->4->4->5 删除后: 1->2->5这是在前一道题目上的延伸。
解法一：
结合前两题的方式，可以拆分处理，先用第4题的方式删除重复的数字并记录下来，再第3题的方式删除指定数字。
public class Code_06 { public static void main(String[] args) { Code_06 c = new Code_06(); ListNode n = new ListNode(); ListNode head = n; for (int i = 1; i <= 5; i++) { n.next = new ListNode(i); n = n.next; if (i % 2 == 0) { n.next = new ListNode(i); n = n.next; } } System.out.println(head); System.out.println(c.deleteDuplicates(head)); } public ListNode deleteDuplicates(ListNode head) { ListNode cur = head; Set dupSet = new HashSet<>(); while (cur != null && cur.next != null) { if (cur.val != cur.next.val) { cur = cur.next; } else { dupSet.add(cur.val); cur.next = cur.next.next; } } for (Integer val : dupSet) { head = deleteNode(head, val); } return head; } private ListNode deleteNode(ListNode head, int val) { while (head != null) { if (head.val != val) { break; } head = head.next; } ListNode pre = null; ListNode cur = head; while (cur != null) { if (cur.val == val) { pre.next = cur.next; } else { pre = cur; } cur = cur.next; } return head; }} 
当然第一种解法只能当做是编码的练习，出题者肯定不是希望你用这种方式处理。
解法二：
哑节点+双指针
public class Code_06_01 { public static void main(String[] args) { Code_06_01 c = new Code_06_01(); ListNode n = new ListNode(); ListNode head = n; for (int i = 1; i <= 5; i++) { n.next = new ListNode(i); n = n.next; if (i % 2 == 0) { n.next = new ListNode(i); n = n.next; } } System.out.println(head); System.out.println(c.deleteDuplicates(head)); } /** * 哑节点+双指针 * * 构建一个哑节点，让其next指向头位置。 * 再利用双指针，n1,n2,初始都指向head位置，如果n1.next.val==n2.next.val，则让n2向前移动一位，否则n1，n2一起向前移动一位 * * @param head * @return */ public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(); dummy.next = head; ListNode n1 = dummy; ListNode n2 = head; while (n2 != null && n2.next != null) { if (n1.next.val != n2.next.val) { n1 = n1.next; } else { //n2一直移动，直到不等于n1为止 while (n2 != null && n2.next != null && n1.next.val == n2.next.val) { n2 = n2.next; } n1.next = n2.next; } n2 = n2.next; } return dummy.next; }} 
6、合并有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
原链表：l1 = [1,2,4]，l2 = [1,3,4]
合并后：[1,1,2,3,4,4]public class Code_04 { public static void main(String[] args) { ListNode n = new ListNode(1); ListNode l1 = n; for (int i = 3; i <= 5; i = i + 2) { n.next = new ListNode(i); n = n.next; } ListNode n2 = new ListNode(2); ListNode l2 = n2; for (int i = 4; i <= 6; i = i + 2) { n2.next = new ListNode(i); n2 = n2.next; } Code_04 c = new Code_04(); System.out.println("原链表1：" + l1); System.out.println("原链表2：" + l2); System.out.println("合并后：" + c.mergeTwoLists(l1, l2)); } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } ListNode mergeNode = new ListNode(); ListNode pre = mergeNode; //比较两个链表当前的值，值小的链表就把引用赋给mergeNode，并向后移动一位重新赋值给自己，同时pre指向值小的那个节点 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 mergeNode.next; }} 
7、双向链表实现栈、队列
队列：先进先出
栈：先进后出
分别用双向链表实现，从头进，从头出，从尾进，从尾出即可模拟出队列和栈的数据结构。
public class NodeUtils{ DoubleListNode head; DoubleListNode tail; /** * 从头进 * @param data */ public void addHead(T data) { DoubleListNode node = new DoubleListNode(data); if (head == null) { head = node; tail = node; } else { node.next = head; head.last = node; head = node; } } /** * 从尾进 * @param data */ public void addTail(T data) { DoubleListNode node = new DoubleListNode(data); if (head == null) { head = node; } else { tail.next = node; node.last = tail; } tail = node; } /** * 从头出 * @return */ public T popHead() { if (head == null) { return null; } DoubleListNode h = head; if (head == tail) { head = null; tail = null; } else { head = head.next; head.last = null; } return h.data; } /** * 从尾出 * @return */ public T popTail() { if (tail == null) { return null; } DoubleListNode t = tail; if (head == tail) { head = null; tail = null; } else { tail = tail.last; tail.next = null; } return t.data; }}
队列
/** * 队列（先进先出）：从链表头进，从链表尾出 * @param*/public class ListNodeQueue { NodeUtils nodeUtils = new NodeUtils(); public void push(T data) { nodeUtils.addHead(data); } public T pop() { return nodeUtils.popTail(); }}
栈
/** * 队列（先进先出）：从链表头进，从链表尾出 * * @param*/public class ListNodeQueue { NodeUtils nodeUtils = new NodeUtils(); public void push(T data) { nodeUtils.addHead(data); } public T pop() { return nodeUtils.popTail(); }}
验证
public class Code_07 { public static void main(String[] args) { ListNodeStack stack = new ListNodeStack(); stack.push(1); stack.push(2); stack.push(3); System.out.println("栈：压进去1,2,3"); System.out.println("弹出" + stack.pop() + "," + stack.pop() + "," + stack.pop()); ListNodeQueue queue = new ListNodeQueue(); queue.push(1); queue.push(2); queue.push(3); System.out.println("队列：压进去1,2,3"); System.out.println("弹出" + queue.pop() + "," + queue.pop() + "," + queue.pop()); }} 
转载地址：http://uqlrb.baihongyu.com/
你可能感兴趣的文章
设计模式03_工厂
查看>>
设计模式04_抽象工厂
查看>>
设计模式05_单例
查看>>
设计模式06_原型
查看>>
设计模式07_建造者
查看>>
设计模式08_适配器
查看>>
设计模式09_代理模式
查看>>
设计模式10_桥接
查看>>
设计模式11_装饰器
查看>>
设计模式12_外观模式
查看>>
设计模式13_享元模式
查看>>
设计模式14_组合结构
查看>>
设计模式15_模板
查看>>
海龟交易法则01_玩风险的交易者
查看>>
CTA策略02_boll
查看>>
vnpy通过jqdatasdk初始化实时数据及历史数据下载
查看>>
设计模式19_状态
查看>>
设计模式20_观察者
查看>>
vnpy学习10_常见坑02
查看>>
用时三个月，终于把所有的Python库全部整理了！拿去别客气！
查看>>