一、LC141 是否有环结构
public boolean hasCycle(ListNode head) { Set<ListNode> set = new HashSet<>(); while (head != null) { //如果重复出现说明有环 if (set.contains(head)) return true; //否则就把当前节点加入到集合中 set.add(head); head = head.next; } return false; }
二、LC234 是否为回文链表
public boolean isPalindrome(ListNode head) { ListNode node1 = head; ListNode node2 = head; Stack<Integer> stack = new Stack<>(); while(node1 != null) { stack.push(node1.val); node1 = node1.next; } while(node2 != null) { if(node2.val == stack.peek()) { stack.pop(); } else { return false; } node2 = node2.next; } return true; }
三、LC21 合并两个有序链表
public 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; } }
四、LC83 删除链表中的重复元素
public ListNode deleteDuplicates(ListNode head) { if (head == null) return head; while(head.next != null){ if (head.val == head.next.val){ head.next = head.next.next; }else { head = head.next; } } return head; }
五、LC203 移除链表元素
public ListNode removeElements2(ListNode head, int val) { while (head != null && head.val == val) { head = head.next; } ListNode prev = head; if (prev != null) { while (prev.next != null) { if (prev.next.val == val) prev.next = prev.next.next; else prev = prev.next; } } return head; }
六、LC206 反转链表
public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode node = reverseList(head.next); head.next.next = head; head.next = null; return node; }
七、Offer22 返回链表倒数第K个元素
class Solution { public int kthToLast(ListNode head, int k) { List<Integer> list = new ArrayList<>(); while (head != null) { list.add(head.val); head = head.next; } return list.get(list.size() - k); } }
