四、链表 Linked List

1.1 链表是什么？

1.2 链表常用的操作

1.3 java代码

package LinkedListTest;

import java.util.LinkedList;

/**
 * @author wzt
 */
public class LinkedListTest {
    public static void main(String[] args) {

        // Create a LinkedLists
        LinkedList<Integer> linkedList = new LinkedList<>();

        // Add Element
        // Time Complexity: O(1)
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        // [1, 2, 3];
        System.out.println(linkedList);

        // Insert element
        // Time Complexity O(N)
        linkedList.add(2, 99);
        // [1, 2, 99, 3]
        System.out.println(linkedList);

        // Access Element
        // Time Complexity: O(N)
        int element = linkedList.get(2);
        // 99
        System.out.println(element);

        // Search Element
        // Time complexity: O(N)
        int index = linkedList.indexOf(99);
        // 2
        System.out.println(index);

        // Update Element
        // Time Complexity:O(N)
        linkedList.set(2, 88);
        // [1, 2, 88, 3]
        System.out.println(linkedList);

        // Remove Element
        // Time Complexity: O(N)
        linkedList.remove(2);
        // [1, 2, 3]
        System.out.println(linkedList);

        // Length
        // Time Complexity: O(1)
        int length = linkedList.size();
        // 3
        System.out.println(length);
    }
}

1.4 leetcode 203题

题目

解题思路

伪代码

java代码

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        while(head != null){
            if(head.val == val){
                prev.next = head.next;
            }else{
                prev = head;
            }
            head = head.next;
        }
        return dummy.next;
    }
}

1.5 leetcode 206题

题目：

解题思路：

伪代码

java代码

/**
 * @author wzt
 * 反转一个单链表
 */
public class d206 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        head.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
    }

    public static ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        while(head != null && head.next != null){
            ListNode dnext = dummy.next;
            ListNode hnext = head.next;
            dummy.next = hnext;
            head.next = hnext.next;
            hnext.next = dnext;
        }
        // 返回头结点
        return dummy.next;
    }
}

// class ListNode{
//    int val;
//     ListNode next;
//     ListNode(){
//
//    }
//     ListNode(int val){
//        this.val = val;
//    }
//    ListNode(int val, ListNode next){
//        this.val = val;
//        this.next = next;
//    }
// }