做响应式网站怎么设计,提供提供手机网站建设,wordpress 产品筛选,asp网站开发人员招聘题目描述给定一个编码链表和一个加密条件K#xff0c;对编码进行加密。加密规则#xff1a;把编码从前往后开始数第K个元素和从后往前数第K个元素进行交换。注意#xff1a;编码的长度为0.第一个编码的序号是1.示例#xff1a;输入#xff1a;[1 2 3 4 5 6] 2输出#xf… 题目描述给定一个编码链表和一个加密条件K对编码进行加密。加密规则把编码从前往后开始数第K个元素和从后往前数第K个元素进行交换。注意编码的长度为0.第一个编码的序号是1.示例输入[1 2 3 4 5 6] 2输出[1 5 3 4 2 6]链表节点定义如下public class ListNode { int val; ListNode next; ListNode(int x) { val x; }}解题思路1.万能暴力法解决2.先后指针法参考代码package com.lingluo;import java.util.ArrayList;import java.util.List;/** * author 灵洛 * date 2020/8/9 23:05 */public class SwapLinkList { /** * 万能暴力法(适用于在链表中插入/删除节点、反向输出链表、链表排序、翻转链表、合并链表等) * * 使用数组/线性表/map缓存链表节点信息按照提意处理后再转回链表 * param head * param k * return */ public static ListNode swap(ListNode head, int k) { ListNode root head; List list new ArrayList();while (head ! null) { list.add(head.val); head head.next; }//记录交换节点的位置及取值int leftIndex k - 1;int rightIndex list.size() - k;int leftVal list.get(leftIndex);int rightVal list.get(rightIndex);// 从第一个开始 ListNode start root;while (start ! null) {//找到正数第K个元素if (leftIndex 0) { start.val rightVal; }//找到倒数第K个元素if (rightIndex 0) { start.val leftVal; } start start.next; leftIndex--; rightIndex--; }return root; }/** * 先后指针法(用来寻找链表中第K个节点) * 先发指针走K-1步再让后发指针从头节点开始走 * 先发指针走到最后一个节点时后发指针走到倒数第K个节点 * * param head * param k * return */public static ListNode swapByPointer(ListNode head, int k) { ListNode earlier head;// 先发指针先走K-1步for (int i 0; i k - 1 ; i) { earlier earlier.next; }// 记录一下第K个位置的节点用于后面的交换 ListNode mark1 earlier; ListNode later head;// 先后指针一起走先发指针走到最后一个节点时后发指针走到倒数第K个节点while (earlier ! null) { earlier earlier.next; later later.next; }// 交换两个位置的值int mark2 later.val; later.val mark1.val; mark1.val mark2;return head; }//打印public static void printLink(ListNode head) { ListNode curNode head;while (curNode ! null) { System.out.print(curNode.val ); curNode curNode.next; } System.out.println(); }public static void main(String[] args) { ListNode node1 new ListNode(1); ListNode node2 new ListNode(2); ListNode node3 new ListNode(3); ListNode node4 new ListNode(4); ListNode node5 new ListNode(5); node1.next node2; node2.next node3; node3.next node4; node4.next node5; printLink(node1); swap(node1, 2); printLink(node1); }}
