指针强化训练—1— 链表就地逆置 Java C

以单链表作为存储结构，实现线性表的就地逆置。

Java实现

package com.programmercarl.linkedlist.homework;import lombok.AllArgsConstructor;
import lombok.Builder;/*** @ClassName ListNode* @Descriotion 单链表的结点* @Author nitaotao* @Date 2022/5/2 17:24* @Version 1.0**/
@AllArgsConstructor
@Builder
public class ListNode {/*** 结点的值*/public Integer val;/*** 下一个结点*/public ListNode next;/*** 无参构造*/public ListNode() {}/*** 带参构造 1*/public ListNode(int val) {this.val = val;}/*** 带参构造 2*/public ListNode(int val, ListNode next) {this.val = val;this.next = next;}@Overridepublic String toString() {ListNode cur = this;while (cur.next != null&&cur.next!=this) {System.out.print(cur.val+" ");cur=cur.next;}System.out.println(cur.val);return null;}
}package com.programmercarl.linkedlist.homework;/*** @ClassName ListReverse* @Descriotion TODO* @Author nitaotao* @Date 2022/5/5 13:31* @Version 1.0**/
public class ListReverse {public static void main(String[] args) {ListNode node5 = ListNode.builder().val(5).next(null).build();ListNode node4 = ListNode.builder().val(4).next(node5).build();ListNode node3 = ListNode.builder().val(3).next(node4).build();ListNode node2 = ListNode.builder().val(2).next(node3).build();ListNode node1 = ListNode.builder().val(1).next(node2).build();listReverse(node1);}public static void listReverse(ListNode node) {//当前结点ListNode temp1 = new ListNode();//当前结点下一个结点ListNode temp2 = new ListNode();//处理头结点if (node == null) {return;}//只有1个结点if (node.next == null) {System.out.println(node.val);return;} else {temp1.next = node;if (node.next.next != null) {temp2.next = node.next;node.next = null;} else {//只有2个结点node.next.next = node;node.next = null;return;}}//当有下个结点ListNode temp;while (temp2.next.next != null) {//下下个结点temp = ListNode.builder().next(temp2.next.next).build();//原链表结点断开，变换temp2.next.next = temp1.next;//当前结点后移temp1.next = temp2.next;//当前结点下一个结点后移temp2.next = temp.next;}//最后一个结点temp2.next.next = temp1.next;node.next = temp2.next;}
}

C实现

//
// Created by nitaotao on 2022/5/7->
//#include 
#include //单链表的就地逆置
//定义结点
typedef struct ListNode {int val;struct ListNode *next;
} Node, *ListNode;/*** 链表逆置* @param node* 思路：* 原链表断开，后半部分结点一个个从头断开* 一个个加入到前半部分的头部*/
void listReverse(ListNode node) {//指向第一段的虚拟头指针ListNode temp1 = (ListNode) malloc(sizeof(ListNode));//指向第二段的虚拟头指针ListNode temp2 = (ListNode) malloc(sizeof(ListNode));//处理头结点if (node == NULL) {return;}//只有1个结点if (node->next == NULL) {printf("%d", node->val);return;} else {//如果不止一个结点//temp1指向当前结点temp1->next = node;//如果有第三个结点if (node->next->next != NULL) {//下一个结点的指针指向第二个结点temp2->next = node->next;//第一个结点断开node->next = NULL;} else {//只有2个结点//第二个结点的下一个指向第一个结点node->next->next = node;//第一个结点断开node->next = NULL;return;}}//此时，整个链表分为两端//第一段为已逆序，第二段为未逆序//temp1指向第一段的头指针，temp2指向第二段的头指针//当第二段有下个结点ListNode temp = (ListNode) malloc(sizeof(ListNode));while (temp2->next->next != NULL) {//temp指向第二段的第二个结点temp->next = temp2->next->next;//指向第二段的头指针  temp2->next//它的next本来是指向第二段的第二个元素，现在断开，指向第一段的头指针指向的元素temp2->next->next = temp1->next;//第一段的虚拟头指针左移temp1->next = temp2->next;//第二段的虚拟头指针 替换 temp 重新指向第二段的第一个结点temp2->next = temp->next;}//当第二段没有下下个结点，即只有下一个结点时，这个结点的下一个直接指向第一段虚拟头指针指向的元素即可temp2->next->next = temp1->next;
}
void showPoint(ListNode node){while (node->next != NULL) {printf("%d", node->val);node = node->next;}//当没有下一个元素了printf("%d", node->val);
}int main() {ListNode node5 = (ListNode) malloc(sizeof(ListNode));node5->val = 5;node5->next = NULL;ListNode node4 = (ListNode) malloc(sizeof(ListNode));node4->val = 4;node4->next = node5;ListNode node3 = (ListNode) malloc(sizeof(ListNode));node3->val = 3;node3->next = node4;ListNode node2 = (ListNode) malloc(sizeof(ListNode));node2->val = 2;node2->next = node3;ListNode node1 = (ListNode) malloc(sizeof(ListNode));node1->val = 1;node1->next = node2;listReverse(node1);showPoint(node5);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！