Java教程

11.22-刷题日记

本文主要是介绍11.22-刷题日记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

24. 两两交换链表中的节点icon-default.png?t=LA92https://leetcode-cn.com/problems/swap-nodes-in-pairs/

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

 输入:head = [1,2,3,4]

输出:[2,1,4,3]

 想法:

  • 还是跟之前一样,设计链表“重组”之类,都用“虚头节点”,最后返回ans.next就行
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode ans = new ListNode(0);
        ans.next = head;
        ListNode cur = ans;
        while(cur.next!=null && cur.next.next!=null){
            ListNode n1 = cur.next;
            ListNode n2 = cur.next.next;
            cur.next = n2;
            n1.next = n2.next;
            n2.next = n1;
            cur = n1;
        }
        return ans.next;
    }
}

707. 设计链表icon-default.png?t=LA92https://leetcode-cn.com/problems/design-linked-list/

get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

 想法:

  • 不要忘记增加ListNode这个类,之前写链表的题目,都会直接给,这次要自己写;
  • 主要就是定义size和head,然后时刻注意size变化;
class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val =x;
    }
}
class MyLinkedList {

    int size;
    ListNode head;
    public MyLinkedList() {
        size=0;
        head = new ListNode(0);
    }
    
    public int get(int index) {
        if(index >= size || index< 0)
            return -1;
        ListNode p = head;
        for(int i=0;i<index+1;i++)
            p = p.next;
        return p.val;          
    }   
    
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index>size) return;
        if(index < 0)  index=0;
        size++;
        ListNode pre = head;
        for(int i=0;i<index;i++)
            pre =pre.next;
        ListNode add = new ListNode(val);
        add.next = pre.next;
        pre.next = add;
    }
    
    public void deleteAtIndex(int index) {
        if(index<0 || index>=size) 
            return;
        size--;
        ListNode pre = head;
        for(int i=0;i<index;i++)
            pre =pre.next;
        pre.next = pre.next.next;
    }
}

这篇关于11.22-刷题日记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!