C/java/python-链表逆序
链表逆序问题描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
解题思路：直接逆转链表 ：将设置两个变量，next保存当前的下一个节点，和一个中转的节点prev
第一步：将当前节点的下一个节点保存在next变量中；
第二步：将当前节点的下一个指向prev；
第三步：将head赋给prev，即prev向前移动；
第四步：将next赋值给head，即head向后移动；
接着循环，直到遍历完链表为止；
一、C语言链表逆序
1、直接逆序
List链表的结构体:
struct List{
int val;
struct List *next;
};
// 直接逆转链表
struct List* dirReverseList(struct List* head){
struct List *prev = NULL;
struct List *next = NULL;
while(head){
struct List *next = head->next;
//next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
2、头插法逆序
// 头插法链表逆转
struct List* reverseList(struct List* head){
struct List temp;
temp.next = NULL;
while(head){
struct List* next = head->next;
head->next = temp.next;
temp.next = head;
head = next;
}
return temp.next;
}
3、打印函数
void printList(List* head,const char* name){
printf("%s:\t",name);
if(!head){
printf("NULL\n");
return;
}
while(head){
printf("[%d]", head->val);
head = head->next;
}
printf("\n");
}
4、主函数
List a,b,c,d;
a.val = 1;
b.val = 2;
c.val = 3;
d.val = 4;
a.next = &b;
b.next = &c;
c.next = &d;
d.next = NULL;
List* head = &a;
printf("------------头插法/直接链表逆转-----------------\n");
printList(head,"old list");
head =dirReverseList(&a);
//head = reverseList(&a);
printList(head,"new list");
5、运行结果
old list: [1][2][3][4]
new list: [4][3][2][1]
Press any key to continue
二、java链表逆序
1、直接逆序
// 迭代法，直接逆转
public static ListNode iterator(ListNode head){
ListNode temp=null,next;
while(head!=null){
next=head.next;
head.next=temp;
temp=head;
head=next;
}
return temp;
}
2、头插法逆序
// 头插法
public static ListNode headInsert(ListNode head){
ListNode next;
ListNode temp = new ListNode();
temp.next=null;
while (head != null){
next = head.next;
head.next = temp.next;
temp.next = head;
head = next;
}
return temp.next;
}
3、打印函数
public static void printList(ListNode node){
while (node != null){
System.out.printf(node.val + " ");
node = node.next;
}
System.out.println();
}
4、主函数
ListNode node6 = new ListNode(6,null);
ListNode node5 = new ListNode(5,node6);
ListNode node4 = new ListNode(4,node5);
ListNode node3 = new ListNode(3,node4);
ListNode node2 = new ListNode(2,node3);
ListNode node1 = new ListNode(1,node2);
printList(node1);
ListNode reverseNode = iterator(node1);
printList(reverseNode);
//System.out.println("------------------");
//ListNode node = headInsert(node1);
//printList(node);
5、运行结果
1 2 3 4 5 6
------------------
6 5 4 3 2 1
三、Python链表逆序
1、代码
# coding: utf-8
# __author__="星仔"
# Email: 6316@qq.com
# Date: 2021/9/28 0028
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
@staticmethod
def reverse(Head):
temp = ListNode()
while Head is not None:
next = Head.next
Head.next = temp.next
temp.next = Head
Head = next
return temp.next
def printList(Head, name):
print("%s:" % name, end="\t")
if Head is None:
print('NULL')
return
while Head is not None:
print('[%d]' % Head.val, end='')
Head = Head.next
print('')
if __name__ == '__main__':
a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)
e = ListNode(5)
a.next = b
b.next = c
c.next = d
d.next = e
printList(a, "old list")
solution = Solution()
head = solution.reverse(a)
printList(head, 'reverse list')
2、运行结果
E:\pythonProject\venv\Scripts\python.exe E:/pythonProject/9-28/algorithm/reverseList.py
old list: [1][2][3][4][5]
reverse list: [5][4][3][2][1]
进程已结束，退出代码为 0