算法Day-4

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

本题意思为要求我们两两交互链表中的节点，而不是直接修改链表的值

我们可以定义一个虚拟头节点，让其指向头节点，从而使头节点和下一个节点进行交互。       

再while循环中判断如果cur.next不为空并且cur.next.next也不为空时才能进行交互，意思是当虚拟头节点的下两位有节点才能交互。然后在交互的过程中首先要将cur指向它的下两位，为了避免头节点找不到我们需要事先将头节点存入临时节点中，并且将第三位节点也就是转换完要连接的节点也保存下来这里叫它第三节点。将cur 指向第二节点后，将cur.next.next指向头节点我们刚刚保存的临时节点，在将cur.next.next.next指向第三节点。然后将cur向下移动两个节点。依次循环

    /**
    * Definition for singly-linked list.
    * public class ListNode {
    *     public int val;
    *     public ListNode next;
    *     public ListNode(int val=0, ListNode next=null) {
    *         this.val = val;
    *         this.next = next;
    *     }
    * }
    */
    public class Solution {
        public ListNode SwapPairs(ListNode head) {
            ListNode dummyNode= new ListNode();
            dummyNode.next = head;
            ListNode cur = dummyNode;
            while(cur.next!=null&&cur.next.next!=null){
                ListNode firstNode = cur.next;
                ListNode thirdNode = cur.next.next.next;
                cur.next = cur.next.next;
                cur.next.next = firstNode;
                cur.next.next.next = thirdNode;

                cur = cur.next.next;
            }
            return dummyNode.next;
        }
    }

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

本题思路，因为链表没有直接获取长度的方法，我们可以使用双指针，快慢指针进行定义并且赋值为虚拟头节点，然后我们让快指针先移动n个节点因为要删除倒数第n个节点，我们让快慢指针相差n个节点就可以实现当快指针移动到next为null时慢指针正好在要删除的节点前一个从而实现删除操作。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(0,head);
        ListNode fast = dummyNode;
        ListNode slow = dummyNode;
        for(int i = 0;i<n;i++){
            fast = fast.next;
        }
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyNode.next;
    }
}

该题输入相交值为val，和相交节点的在每个链表的位置。从0开始，我们需要返回相交节点为头节点的链表，这里我们将两个链表头节点赋值个两个临时节点，遍历这两个链表，如果当前节点不为空就指向当前链表下一个，如果为空就将另一个链表赋值给当前节点，再次遍历，两个节点相等，结束返回一个即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        while(p!=q){
            p = p==null?headB:p.next;
            q = q==null?headA:q.next;
        }
        return p;
    }
}

原文地址：https://blog.csdn.net/zzexcellent27/article/details/143083041

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！