2024-08-13

ListNode是一个在进行链表操作时常用的数据结构,它通常用于表示链表中的一个节点。在Python中,我们可以通过定义一个类来实现ListNode。

以下是一个简单的实现:




class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

在这个定义中,ListNode有一个值域(val)和一个指向下一个节点的指针(next)。

以下是一些使用ListNode的常见操作:

  1. 创建链表



node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
 
node1.next = node2
node2.next = node3
  1. 遍历链表



current = node1
while current is not None:
    print(current.val)
    current = current.next
  1. 添加节点



new_node = ListNode(4)
node1.next = new_node
new_node.next = node2
  1. 删除节点



node1.next = node2.next
  1. 查找节点



current = node1
while current is not None and current.val != value:
    current = current.next
return current
  1. 插入节点



current = node1
while current.next is not None and current.next.val < new_node.val:
    current = current.next
new_node.next = current.next
current.next = new_node
  1. 删除节点



current = node1
while current.next is not None and current.next.val != value:
    current = current.next
current.next = current.next.next

以上就是ListNode的一些基本操作,在实际应用中,你可以根据需要进行相应的扩展和修改。

2024-08-11

以下是一个简单的Java代码示例,演示了如何初始化一个线性表的链表结构,并添加一个元素。




class Node<T> {
    T data;
    Node<T> next;
 
    public Node(T data) {
        this.data = data;
        this.next = null;
    }
}
 
public class LinkedList<T> {
    private Node<T> head;
 
    public LinkedList() {
        head = null;
    }
 
    public void add(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
        } else {
            Node<T> current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }
 
    // 其他方法,例如打印链表、插入节点、删除节点等
}
 
public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(1); // 添加元素1到链表
        // 此处可以添加更多的方法调用来演示其他功能
    }
}

这个示例定义了一个泛型的Node类来表示链表节点,以及一个LinkedList类,它有一个head节点作为链表的开始,并且有一个add方法来向链表添加新的节点。在main方法中,我们创建了一个LinkedList实例,并向其添加了一个整数1。这个简单的示例展示了如何初始化一个链表并添加元素。

2024-08-09



/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil {
        return nil
    }
 
    // 计算链表长度
    length := 1
    current := head
    for current.Next != nil {
        current = current.Next
        length++
    }
 
    // 计算旋转次数
    rotateTimes := length - k%length
    if rotateTimes == length {
        return head
    }
 
    // 找到旋转起始点的前一个节点
    current.Next = head
    for i := 0; i < length - rotateTimes - 1; i++ {
        current = current.Next
    }
 
    // 新的头节点是旋转起始点的下一个节点
    newHead := current.Next
    current.Next = nil
 
    return newHead
}

这段代码首先检查了链表是否为空,并计算了链表的长度。然后根据需要旋转的次数计算出实际需要旋转的次数,以防k大于链表长度时。接着找到新的头节点,并将整个链表形成一个环,最后断开环的部分并返回新的头节点。

2024-08-08

以下是一个针对LeetCode上经典问题的Java代码解法示例,这个问题是关于删除链表中的重复节点。




// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
 
    ListNode(int x) {
        val = x;
        next = null;
    }
}
 
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
 
        ListNode current = head;
        while (current.next != null) {
            if (current.val == current.next.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
 
        return head;
    }
}

这段代码首先检查链表是否为空,然后遍历链表,如果发现相邻节点值相同,则删除后续重复的节点。最后返回处理后的链表头节点。这是一个典型的对链表进行节点删除操作的解法,适用于解决LeetCode上的其他相关问题。

2024-08-07

在Java中,LinkedList是一个实现了List接口的链表数据结构,它允许在近乎于零的时间内对列表的首部或尾部进行插入和删除操作。LinkedList还可以用作队列或栈。

以下是一些常用的LinkedList方法:

  • add(E e): 在列表的尾部添加元素。
  • add(int index, E element): 在指定位置插入元素。
  • remove(int index): 移除列表中指定位置的元素。
  • remove(Object o): 移除列表中第一次出现的指定元素。
  • get(int index): 返回列表中指定位置的元素。
  • set(int index, E element): 用指定元素替换列表中指定位置的元素。
  • addFirst(E e): 将元素添加到列表的开头。
  • addLast(E e): 将元素添加到列表的末尾。
  • getFirst(): 返回列表的第一个元素。
  • getLast(): 返回列表的最后一个元素。
  • removeFirst(): 移除并返回列表的第一个元素。
  • removeLast(): 移除并返回列表的最后一个元素。
  • peek(): 查看队列的第一个元素,但不移除。
  • poll(): 移除并返回队列的第一个元素。
  • push(E e): 将元素推入栈顶。
  • pop(): 移除栈顶元素。

示例代码:




import java.util.LinkedList;
 
public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
 
        // 添加元素
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
 
        // 在首部添加元素
        linkedList.addFirst("0");
 
        // 在尾部添加元素
        linkedList.addLast("D");
 
        // 查看元素
        System.out.println(linkedList); // 输出: [0, A, B, C, D]
 
        // 获取首元素
        System.out.println(linkedList.getFirst()); // 输出: 0
 
        // 获取尾元素
        System.out.println(linkedList.getLast()); // 输出: D
 
        // 移除首元素
        linkedList.removeFirst();
 
        // 移除尾元素
        linkedList.removeLast();
 
        // 查看元素
        System.out.println(linkedList); // 输出: [A, B, C]
 
        // 使用栈的方式使用LinkedList
        LinkedList<String> stack = new LinkedList<>();
        stack.push("A");
        stack.push("B");
        System.out.println(stack); // 输出: [B, A]
        System.out.println(stack.pop()); // 输出: B
        System.out.println(stack.pop()); // 输出: A
 
        // 使用队列的方式使用LinkedList
        LinkedList<String> queue = new LinkedList<>();
        queue.offer("A");
        queue.offer("B");
        System.out.println(queue); // 输出: [A, B]
        System.out.println(queue.poll()); // 输出: A
        System.out.println(queue.poll()); // 输出: B
    }
}

以上代码演示了\`

2024-08-06

以下是针对LeetCode上第24题和第19题的Go语言解法:

第24题:两两交换链表中的节点




/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 
func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{0, head}
    p := dummy
    for p.Next != nil && p.Next.Next != nil {
        a, b := p.Next, p.Next.Next
        p.Next = b
        a.Next = b.Next
        b.Next = a
        p = a
    }
    return dummy.Next
}

第19题:删除链表的倒数第N个节点




/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{0, head}
    p, q := dummy, dummy
    for i := 0; i < n+1; i++ {
        q = q.Next
    }
    for q != nil {
        p = p.Next
        q = q.Next
    }
    p.Next = p.Next.Next
    return dummy.Next
}

这两个解法都使用了快慢指针或者使用计数来找到要删除的节点的前一个节点,然后通过简单的操作删除目标节点。